3

我正在寻找有关动态编程问题的一些指示。我找不到任何有关如何解决此类问题的相关信息。

问题

 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++).

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

4

2 回答 2

1

让是最后一位为零f(d,x)的最高有效数字的数量，其中 0 ≤ ≤ 2。对于> 1，我们有递归：dxxd

f(d,0) = (f(d-1,0) + f(d-1,1) + f(d-1,2)) * 9 // f(d,0) 来自任何 d- 1 位模式附加了一个非零数字
f(d,1) = f(d-1,0) // f(d,1) 来自 d-1 位数字模式，没有尾随零附加一个零
f(d,2) = f(d-1,1) // f(d,2) 来自 d-1 个数字模式，其中一个尾随零加上一个零

对于d= 1，我们有f(1,0) = 9, f(1,1) = 0, f(1,2) = 0.

原始问题的最终答案是f(d,0) + f(d,1) + f(d,2)。

这是一个用于演示的简单 C 程序：

#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;
}
于 2012-07-26T12:46:23.830 回答
0

NOTE: i haven't tested out my logic thoroughly, so please point out where i might be wrong.

The recurrence for the problem can be

f(d)=f(d/2)*f(d-d/2)-( f(d/2-1)*f(d-d/2-2) + f(d/2-2)*f(d-d/2-1) ) f(0)=1;f(1)=10;f(2)=100;f(3)=999;

here, f(i) is the total number special digits that can be formed considering that '0' can occur as the first digit. So, the actual answer for a 'd' digit number would be 9*f(d-1).

You can easily memoize the recurrence solution to make a DP solution.

I haven't tried out the validity of this solution, so it might be wrong. Here is my logic:

for f(d), divide/partition the number into d/2 and (d-d/2) digit numbers, add the product of f(d)*f(d-d/2). Now, to remove the invalid cases which may occur across the partition we made, subtract f(d/2-1)*f(d-d/2-2) + f(d/2-2)*f(d-d/2-1) from the answer (assume that three zero occur across the partition we made). Try it with paper and pen and you will get it.

于 2012-07-22T15:51:16.110 回答