CODEWITHSUNDEEP
c++algorithmdynamic-programming
Sharad
Sharad

Reputation: 1058

Finding optimal substructure

I'm looking for some pointers about a dynamic programming problem. I cannot find any relevant information about how to solve this kind of problem.

Problem 

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

Problem can easily solved by permutation and combination but i want it with dynamic programming. I am unable to find its optimal substructure or bottom to top approach.

Upvotes: 3

Views: 420

Answers (2)

RoBa
RoBa

Reputation: 428

Let f(d,x) be the amount of most significant d digits whose last x digits are zeros, where 0 ≤ x ≤ 2. For d > 1, We have the recurrence:

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 zero
f(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;
}

Upvotes: 1

nims
nims

Reputation: 3871

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.

Upvotes: 0

Related Questions