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

1 Like

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.

1 Like
//