Dynamic programming ->SPOJ_9570

I am new to Dynamic programming,never solved such kind of question before.Can some1 please provide me detailed explanation of how to identify next state and thus find recurrence relation .Please i would be highly grateful

1 Like

For basics Click here
Hope this might help you.
Problems click problems to move to examples.
Enjoy coding.Happy Day…:slight_smile:

1 Like

You need to expand the solution state for this one, at least that’s how I did it. Instead of finding f(n,k) try to find f(n,k,q) where n- number of bits,k - largest substring of 1s , q - ending with q 1s