akashcserocks's blog

Stuck with this dp problem in Spoj : http://www.spoj.com/problems/GNYR09F/

By akashcserocks, history, 7 years ago, In English

Here is the ideone link to my code : http://ideone.com/TdjqlG

What I'm doing is that I'm passing the last bit visited as a parameter and based on whether the bit is 0 or 1 ,doing 2 separate sets of recursive calls. I'm assuming that instead of n element array, the array is of n+1 elements and the (n+1)the element is always 0. Please help!

  • Vote: I like it
  • +5
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The problem is that you're losing some of the necessary data which should be rather saved, you should extend your dp state to be dp[i][j][k] that corresponds to the string which has length i and its adjacentbitcount is j and the last bit of it is k.
Your code is almost correct, just memorize the parameter of last bit into your DP array.

Worth to say, this solution will likely get TLE, you don't have to calculate the DP array over and over again, just declare the array as a global one and then your code would be of order O(N.K + T) which is now O(N.K.T).

→ Reply