algorithm - 动态规划算法查找可被 3 整除的 n 位数字的数量

Question

给出下列问题的动态规划解决方案。给定一个数 n>0， 计算能被 3 整除的 n 位自然数的个数，并且不 包含数字“1”。

提示:表格的大小为 n×3

我为此苦恼了好几天，却找不到解决方案。

Answer 1

动态规划通常涉及将较小子问题的解决方案组合在一起的递归关系。

对于你的问题，请注意一个数要被 3 整除，它的数字总和必须能被 3 整除。设:

dp[i, s] = how many numbers with i digits have sum of digits s

我们有:

dp[i, s] = dp[i - 1, s] +        <- use digit 0
           dp[i - 1, s - 2] +    <- use digit 2
           dp[i - 1, s - 3] +    <- use digit 3
           ...
           dp[i - 1, s - 9]      <- use digit 9

这确实可以通过使用求和模 3 优化为 n x 3 表(现在是 n x S)。那个和基本案例留作练习，或者至少延迟到你展示一些工作。