dynamic-programming Getting started with dynamic-programming Constructing a DP Solution

Example

No matter how many problems you solve using dynamic programming(DP), it can still surprise you. But as everything else in life, practice makes you better. Keeping these in mind, we'll look at the process of constructing a solution for DP problems. Other examples on this topic will help you understand what DP is and how it works. In this example, we'll try to understand how to come up with a DP solution from scratch.

Iterative VS Recursive:
There are two techniques of constructing DP solution. They are:

• Iterative (using for-cycles)
• Recursive (using recursion)

For example, algorithm for calculating the length of the Longest Common Subsequence of two strings s1 and s2 would look like:

Procedure LCSlength(s1, s2):
Table[0][0] = 0
for i from 1 to s1.length
    Table[0][i] = 0
endfor
for i from 1 to s2.length
    Table[i][0] = 0
endfor
for i from 1 to s2.length
    for j from 1 to s1.length
        if s2[i] equals to s1[j]
            Table[i][j] = Table[i-1][j-1] + 1
        else
            Table[i][j] = max(Table[i-1][j], Table[i][j-1])
        endif
    endfor
endfor
Return Table[s2.length][s1.length]

This is an iterative solution. There are a few reasons why it is coded in this way:

• Iteration is faster than recursion.
• Determining time and space complexity is easier.
• Source code is short and clean

Looking at the source code, you can easily understand how and why it works, but it is difficult to understand how to come up with this solution. However the two approaches mentioned above translates into two different pseudo-codes. One uses iteration(Bottom-Up) and another uses recursion(Top-Down) approach. The latter one is also known as memoization technique. However, the two solutions are more or less equivalent and one can be easily transformed into another. For this example, we'll show how to come up with a recursive solution for a problem.

Example Problem:
Let's say, you have N (1, 2, 3, ...., N) wines placed next to each other on a shelf. The price of ith wine is p[i]. The price of the wines increase every year. Suppose this is year 1, on year y the price of the ith wine will be: year * price of the wine = y*p[i]. You want to sell the wines you have, but you have to sell exactly one wine per year, starting from this year. Again, on each year, you are allowed to sell only the leftmost or the rightmost wine and you can't rearrange the wines, that means they must stay in same order as they are in the beginning.

For example: let's say you have 4 wines in the shelf, and their prices are(from left to right):

+---+---+---+---+
| 1 | 4 | 2 | 3 |
+---+---+---+---+

The optimal solution would be to sell the wines in the order 1 -> 4 -> 3 -> 2, which will give us a total profit of:

Greedy Approach:
After brainstorming for a while, you might come up with the solution to sell the expensive wine as late as possible. So your greedy strategy will be:

Every year, sell the cheaper of the two (leftmost and rightmost) available wines.

Although the strategy doesn't mention what to do when the two wines cost the same, the strategy kinda feels right. But unfortunately, it isn't. If the prices of the wines are:

+---+---+---+---+---+
| 2 | 3 | 5 | 1 | 4 |
+---+---+---+---+---+

The greedy strategy would sell them in the order 1 -> 2 -> 5 -> 4 -> 3 for a total profit of:

But we can do better if we sell the wines in the order 1 -> 5 -> 4 -> 2 -> 3 for a total profit of:

This example should convince you that the problem is not so easy as it looks on the first sight. But it can be solved using Dynamic Programming.

Backtracking:
To come up with the memoization solution for a problem finding a backtrack solution comes handy. Backtrack solution evaluates all the valid answers for the problem and chooses the best one. For most of the problems it is easier to come up with such solution. There can be three strategies to follow in approaching a backtrack solution:

1. it should be a function that calculates the answer using recursion.
2. it should return the answer with return statement.
3. all the non-local variables should be used as read-only, i.e. the function can modify only local variables and its arguments.

For our example problem, we'll try to sell the leftmost or rightmost wine and recursively calculate the answer and return the better one. The backtrack solution would look like:

// year represents the current year
// [begin, end] represents the interval of the unsold wines on the shelf
Procedure profitDetermination(year, begin, end):
if begin > end                  //there are no more wines left on the shelf
    Return 0
Return max(profitDetermination(year+1, begin+1, end) + year * p[begin], //selling the leftmost item
           profitDetermination(year+1, begin, end+1) + year * p[end])   //selling the rightmost item

If we call the procedure using profitDetermination(1, 0, n-1), where n is the total number of wines, it will return the answer.

This solution simply tries all the possible valid combinations of selling the wines. If there are n wines in the beginning, it will check possibilities. Even though we get the correct answer now, the time complexity of the algorithm grows exponentially.

The correctly written backtrack function should always represent an answer to a well-stated question. In our example, the procedure profitDetermination represents an answer to the question: What is the best profit we can get from selling the wines with prices stored in the array p, when the current year is year and the interval of unsold wines spans through [begin, end], inclusive? You should always try to create such a question for your backtrack function to see if you got it right and understand exactly what it does.

Determining State:
State is the number of parameters used in DP solution. In this step, we need to think about which of the arguments you pass to the function are redundant, i.e. we can construct them from the other arguments or we don't need them at all. If there are any such arguments, we don't need to pass them to the function, we'll calculate them inside the function.

In the example function profitDetermination shown above, the argument year is redundant. It is equivalent to the number of wines we have already sold plus one. It can be determined using the total number of wines from the beginning minus the number of wines we have not sold plus one. If we store the total number of wines n as a global variable, we can rewrite the function as:

Procedure profitDetermination(begin, end):
if begin > end
    Return 0
year := n - (end-begin+1) + 1        //as described above
Return max(profitDetermination(begin+1, end) + year * p[begin],
           profitDetermination(begin, end+1) + year * p[end])

We also need to think about the range of possible values of the parameters can get from a valid input. In our example, each of the parameters begin and end can contain values from 0 to n-1. In a valid input, we'll also expect begin <= end + 1. There can be O(n²) different arguments our function can be called with.

Memoization:
We are now almost done. To transform the backtrack solution with time complexity into memoization solution with time complexity , we will use a little trick which doesn't require much effort.

As noted above, there are only different parameters our function can be called with. In other words, there are only different things we can actually compute. So where does time complexity come from and what does it compute!!

The answer is: the exponential time complexity comes from the repeated recursion and because of that, it computes the same values again and again. If you run the code mentioned above for an arbitrary array of n = 20 wines and calculate how many times was the function called for arguments begin = 10 and end = 10, you will get a number 92378. That is a huge waste of time to compute the same answer that many times. What we could do to improve this is to store the values once we have computed them and every time the function asks for an already calculated value, we don't need to run the whole recursion again. We'll have an array dp[N][N], initialize it with -1 (or any value that will not come in our calculation), where -1 denotes the value hasn't yet been calculated. The size of the array is determined by the maximum possible value of begin and end as we'll store the corresponding values of certain begin and end values in our array. Our procedure would look like:

Procedure profitDetermination(begin, end):
if begin > end
    Return 0
if dp[begin][end] is not equal to -1                //Already calculated
    Return dp[begin][end]
year := n - (end-begin+1) + 1
dp[begin][end] := max(profitDetermination(year+1, begin+1, end) + year * p[begin],
           profitDetermination(year+1, begin, end+1) + year * p[end])
Return dp[begin][end]

This is our required DP solution. With our very simple trick, the solution runs time, because there are different parameters our function can be called with and for each of them, the function runs only once with complexity.

Summery:
If you can identify a problem that can be solved using DP, use the following steps to construct a DP solution:

• Create a backtrack function to provide the correct answer.
• Remove the redundant arguments.
• Estimate and minimize the maximum range of possible values of function parameters.
• Try to optimize the time complexity of one function call.
• Store the values so that you don't have to calculate it twice.

The complexity of a DP solution is: range of possible values the function can be called with * time complexity of each call.