dynamic-programming Getting started with dynamic-programming Understanding State in Dynamic Programming

Example

Let's discuss with an example. From n items, in how many ways you can choose r items? You know it is denoted by . Now think of a single item.

• If you don't select the item, after that you have to take r items from remaining n-1 items, which is given by .
• If you select the item, after that you have to take r-1 items from remaining n-1 items, which is given by .

The summation of these two gives us the total number of ways. That is:

If we think nCr(n,r) as a function that takes n and r as parameter and determines , we can write the relation mentioned above as:

nCr(n,r) = nCr(n-1,r) + nCr(n-1,r-1)

This is a recursive relation. To terminate it, we need to determine base case(s). We know that, and . Using these two as base cases, our algorithm to determine will be:

Procedure nCr(n, r):
if r is equal to 1
    Return n
else if n is equal to r
    Return 1
end if
Return nCr(n-1,r) + nCr(n-1,r-1)

If we look at the procedure graphically, we can see some recursions are called more than once. For example: if we take n = 8 and r = 5, we get:

We can avoid this repeated call by using an array, dp. Since there are 2 parameters, we'll need a 2D array. We'll initialize the dp array with -1, where -1 denotes the value hasn't been calculated yet. Our procedure will be:

Procedure nCr(n,r):
if r is equal to 1
    Return n
else if n is equal to r
    Return 1
else if dp[n][r] is not equal to -1        //The value has been calculated
    Return dp[n][r]
end if
dp[n][r] := nCr(n-1,r) + nCr(n-1,r-1)
Return dp[n][r]

To determine , we needed two parameters n and r. These parameters are called state. We can simply deduce that the number of states determine the number of dimension of the dp array. The size of the array will change according to our need. Our dynamic programming algorithms will maintain the following general pattern:

Procedure DP-Function(state_1, state_2, ...., state_n)
Return if reached any base case
Check array and Return if the value is already calculated.
Calculate the value recursively for this state
Save the value in the table and Return

Determining state is one of the most crucial part of dynamic programming. It consists of the number of parameters that define our problem and optimizing their calculation, we can optimize the whole problem.