 # How to formulate a recurrence relation for a DP problem?

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 will be 1, dp will be 2, and dp will be 1. Now for i>=3, dp[i][j]=dp[i-1][j]+dp[i-1][j] and dp[i][j]=dp[i-1][j-1]+dp[i-1][j]. 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.