c++ - 寻找最优子结构

Question

我正在寻找有关动态规划问题的一些建议。我找不到有关如何解决此类问题的任何相关信息。

问题

 A number is called a special number if it doesn't contain 3 consecutive 
 zeroes. i have to calculate the number of positive integers of exactly d digits 
 that are special answer should be modulo 1000000007(just for overflow in c++).

问题可以通过排列组合轻松解决，但我希望通过动态规划解决。我无法找到它的最佳子结构或自下而上的方法。

Answer 1

设 f(d,x) 是最后 x 位为零的最重要 d 位的数量，其中 0 ≤ x ≤ 2。对于 d > 1，我们有递归:

f(d,0) = (f(d-1,0) + f(d-1,1) + f(d-1,2)) * 9  // f(d,0) comes from any d-1 digits patterns appended a non-zero digit f(d,1) = f(d-1,0) // f(d,1) comes from the d-1 digits patterns without tailing zeros appended by a zerof(d,2) = f(d-1,1) // f(d,2) comes from the d-1 digits patterns with one tailing zero appended by a zero

And for d = 1, we have f(1,0) = 9, f(1,1) = 0, f(1,2) = 0.

The final answer for the original problem is f(d,0) + f(d,1) + f(d,2).

Here is a simple C program for demo:

#include <cstdio>

const int MOD = 1000000007;
long long f[128][3];

int main() {
  int n;
  scanf("%d",&n);
  f[1][0] = 9;
  for (int i = 2 ; i <= n ; ++i) {
    f[i][0] = (f[i-1][0] + f[i-1][1] + f[i-1][2]) * 9 % MOD;
    f[i][1] = f[i-1][0];
    f[i][2] = f[i-1][1];
  }
  printf("%lld\n", (f[n][0] + f[n][1] + f[n][2]) % MOD);
  return 0;
}