# 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[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.