Formulating a recurrent relation that connects different states is an important theme in DP problems. However this is the thing I’m struggling with. I’m not good at maths as well.
Example: http://www.spoj.com/problems/GNYR09F/ . I have been trying it for days with no luck. It would be great if someone could show the process of arriving at the DP recurrence( preferably in steps). I don’t want the code or solution. I just want to know the way you arrive at the DP recurrence.
LET US DEFINE dp[i][j][b] as the number of ways you can have the adjacency bit count equal to j for a binary string of size i ending with b ( i.e. b is either 0 or 1) Now, for binary strings of length 1, adjacency bid count will always be 0. For binary strings of length 2, dp[2][1][1] will be 1, dp[2][0][0] will be 2, and dp[2][0][1] will be 1. Now for i>=3, dp[i][j][0]=dp[i-1][j][0]+dp[i-1][j][1] and dp[i][j][1]=dp[i-1][j-1][1]+dp[i-1][j][0]. Hence for all j varying between 0 to i-1 for each i, you will get the number of binary strings of length i you can have with adjacency bit count j , ending with 0 or 1.
Your answer= dp[n][k][0]+dp[n][k][1].
The basic idea for a dp problem is in the name itself;
Dynamic Programming uses previously stored values for creating new values. The key is defining the correct dp.
Generally, dp[n] will be the final answer itself, which helps in defining the dp. Sometimes, the final answer may be the maximum/minimum of all the dp’s. Identifying this mostly comes by practice.
If the dp cannot be defined in one dimension, try to use a multidimensional array for the dp to make the recurrence easier. Sometimes, a single dp may not suffice. If so, use multiple dp’s. Identifying these comes by practice too.
CLRS Introduction to algorithms has some good content on dp’s too.