We will solve a DP problem today.

dp state is (index, tight).

where index is the position where we currently are (consider the process of constructing solution from left to right).

where tight is a variable which states the number which we have constructed up to now, is strictly less/greater or equal. Tight is false, means it has become less or greater. but true when equal.

Ex. 1. http://www.spoj.com/problems/SQAMOD/

find no of binary numbers less than a given n digit number S which have sum of squares of digits modulo 3 to be zero,

Solution:

1. dp (index, int sumModulo3, int tight):

So let us see the transitions to different states. You can understand that by reading the code.

Hi you know other problems seem like this. Tutorial about this Digit DP? Thanks.

ReplyDeleteCan you please help me out with the running time of this solution.

ReplyDeleteIt visits all the possible States (10^5 * 3 *2).

Delete