There were many resources on the Internet that covered dynamic programming but it was difficult to understand. With an example, we will track every input change to provide a better explanation here. Thus, this article is meant to make dynamic programming easier to understand. You should continue reading this article from algo.monster.
Well , this is basically a foundational introduction to dynamic programming algorithm. For those who use brute force, this will give you a better idea of dynamic programming. Now, let’s have a step by step analysis of DP solving a problem.
What is dynamic programming?
Dynamic programming is a algorithm that is popular in solving problems efficiently. Also, it is a powerful optimization method.
Let’s see the formal definition from Wikipedia and here we quote: “Dynamic programming is both a mathematical optimization method and a computer programming method.”
In fact, it is simply a way to save intermediate results from calculations in any format, so you can use them for further computations rather than repeating the calculations. Or to put it in another way, dynamic programming uses a table to store solutions to subproblems that have been solved. Then, you can simply take the solution from the table and solve the subproblem again if you need it. So, the algorithms using dynamic programming are extremely effective.
How can you solve a problem using DP?
These are the tasks you will need to complete in order to solve a dynamic programming problem:
- You can solve the smallest decomposed problem.
- To solve a subproblem, you must find the rule or formula.
- Make a table to store the subproblem solutions. Next, calculate the solution to subproblems using the formula. Save the table.
- You can solve the subproblems and find the solution to the original problem.
How to solve long increasing sequences with dynamic programming?
The LIS or the Longest Increasing Subsequence Problem is to determine the length of the longest sequence of elements such that they are sorted in increasing order. Let’s look at two examples.
LIS is {10, 12, 22, 23, 25, 30}, and the length of LIS for {10, 12, 32, 2, 22, 23, 25, 30} is 6.
Step by step of how we use DP to solve the LIS problem
What would you do to solve this problem? What information would you keep to make it easier? Let’s say that you were asked to solve the problem by brute force, just as you would with a selection sort.
| 10 | 12 | 32 | 2 | 22 | 23 | 25 | 30 |
| k,i | j |
Friend: I would like to compare each element with the other elements. If it is larger than the current one I would increase the count variable. In doing so, it’s possible to get the highest number. The code is as following:
for(i=0;i<n-1;i++)
{
count = 1;
for(j=i+1,k=i;j<n,k<n-1;j++)
{
if(a[j] > a[k])
{
k=j;
count++;
}
if(count>maxi)
maxi = count;
}
}
printf("\nMax-length = %d\n",maxi);
Me: Shall we run the code?
Friend: Yes.
Me: Let’s see the output.
Friend: The result is max-length = 5. I suppose it is probably {2, 22, 23, 24, 25, 25}. However, we know it’s 6, and that the LIS is {10, 12, 22, 23, 25, 30}.
Why is it unable to capture the above LIS?
Me: It will check, because it will traverse {10, 12, 32, 22, 23, 25, 30}.
If(10>12), then the count is 2.
If(32>12), then the count is 3.
From this point on, count = 3. The following elements are less than 32 so condition like (22>32), will not get incremented.
Friend: It would be great if it knew that by traversing the remainder of the array and avoiding 32, we could actually achieve the max-length result = 6.
Me: This result is what we use to compute using dynamic programming. But brute force is the storage of the count variable for every possible traversal in an array. Then, we simply find the maximum. Well, this does not mean brute force can’t solve the problem. A different approach could, but it will be more time-consuming.
NOTE: My friend set count=1 instead of 0 in the beginning because there are cases where all the numbers are equal in the array, that is 2, 2, 2, 2. Since count must be returned as 1, because one element 2 is still part of the larger array.
Solution using dynamic programming
Me: How do we code the same thing in dynamic programming?
Friend: Because you stated that we store counts for all variables, do we also initialize an array with the same size as the corresponding counts?
Me: Right. First, we create another array to store the count of each member of our array. Then, we initialize them all to 1.
Friend: Let’s do a similar check.
Me: Yes, but let’s just assume that element 10 is in the array.
Friend: Why?
Me: To make things simpler! You don’t need to do anything else. Listen along. Let’s see, what is the longest growing subsequence?
Friend: 1 course, LIS is 10.
Me: Now, let’s say we add 12 to the initial count and make it 1.
Friend: Let’s see if (12>10) is checked so that 12’s count gets increased?
Me: Is 12 now counted as 10?, then 12 becomes 10 + 1, since 10 is the longest subsequence of increasing sequence that can be made using the elements. Count of 12 is now 10+12 =10,12 or count[i] = count[j]+1. This is 2.
Friend: Let me clarify this. When 10 was all that existed, LIS was 1. Now that 12 has been added, we discover that 10,12 could be LIS because 12>10. So we add the count of 10’s to 12, and then add 1 to make the number.
Me: It’s correct, and the array becomes:
Conclusion
Dynamic programming works just like any other type of programming algorithm. After all, practice makes your skills perfect.
In fact, DP is very similar to brute force. However, instead of searching the entire input space, dynamic programming discovers a way to store intermediate outcomes that result from the input.
Well, it’s safe to say that dynamic programming needs more space because of that. So, basically it is a way to trade space for time. While recursive approaches may use less space, dynamic programming is faster.
