Sunday, 23 June 2013

Digit Dynamic Programming problem

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.

2 comments:

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

    ReplyDelete
  2. Can you please help me out with the running time of this solution.

    ReplyDelete