What is dynamic programming?
Dynamic programming is basically a technique to optimize the time taken by a recursive algorithm.
Limitations of recursion:
Recursive programs break down the final problem into smaller sub-problems and solve those sub-problems independently, thus, working their way up to the final problem. However, there is a problem in this method. Often, the values of certain sub-problems are calculated multiple times resulting in an unnecessary waste of operations.
Consider the recursive implementation of the Fibonacci sequence. It is explained well in the following post:
In the post we identify a problem in the recursive implementation of the program. It is observed that many operations are being repeated many times. (Read the above post for a better understanding of the problem).
So how can we fix this?
Dynamic programming provides an elegant solution to the above problem. In this kind of programming the values of sub-problems are stored in an external data structure like an array. This prevents repeated calculations of the same problems.
The values once stored in the array need not be calculated again, they only need to be accessed.
Thus, time complexity of the program reduces by a great deal.
We discussed the Fibonacci problem briefly above and in great amount in the linked post. The dynamic programming approach to this would be to store the values of the Fibonacci numbers in an array. This will prevent repeated iterations of the same calculations (like F(2), F(3)).
Different kinds of dynamic programming:
- Bottom-up approach(tabulation):
In this we move from the bottom of the problem to the top.
We start at the simplest part of the problem and solve for what we know. We move up towards the final problem solving and storing the values along the way. The method used in the Fibonacci post made earlier by me(linked above) is an example of a bottom-up approach.
- Top-down approach(memoization):
In this kind of approach, we start at the top of the problem and break the problem into smaller sub-problems, like recursion. However, unlike simple recursion, we store the values of the solved sub-problems. For example, we can restructure our approach to the Fibonacci problem in the following way:
Instead of starting with f(0) and f(1) and working our way up to f(n) we start with f(n) and work our way down to f(0) and f(1), calculate the values, and backtrack to f(n) to finally find the answer.
In this approach we start with f(n). We will represent this as f(n-1) + f(n-2), and we move further in depth to calculate f(n-1).
Now where does DP play into this?
Suppose we have reached f(2).
This will be represented as f(1) + f(0). This comes out to 1. We store the value of f(2).
When we have to find the value of f(3) we will have to calculate f(2)+f(1). Without memoization this would lead to unnecessary repeat of functions. However, since we have stored the value of f(2) as 1, we can directly substitute this value and find that f(3) = 1 + 1 = 2. This reduces the time complexity by a great deal.
Multi-dimensional dynamic programming:
All our considerations till now have only consisted of something called 1-dimensional dynamic programming. In this kind of DP there is only one dependant variable. In the previous cases this was “n” which represented the number till which we had to define the Fibonacci sequence. This is the simplest form of dynamic programming.
Following are some problems of 1-dimensional DP:
a) SUPW (Codechef) – https://www.codechef.com/ZCOPRAC/problems/ZCO14002 (you should expect a post to come with a solution to this problem soon)
b) Count jumps (GeeksForGeeks) – https://www.geeksforgeeks.org/count-number-ways-jump-reach-end/
c) Longest Increasing Subsequence (GeeksForGeeks) – https://www.geeksforgeeks.org/longest-increasing-subsequence-dp-3/
There is another, a little more complicated aspect to dynamic programming. This is multi-dimensional dynamic programming, where there are more than one dependant variables. This can be 2-dimensional and 3-deimensional. We have not discussed these kinds of problems yet. However, I will make a post explaining the solution to a specific 2-dimensional DP problem in the near future. That shall clear up some of the doubts you may be having regarding multi-dimensional dynamic programming to a great extent.
Following are some problems of multi-dimensional DP:
a) Edit Distance (leetCode) – https://leetcode.com/problems/edit-distance/
(you should expect a post to come with a solution to this problem soon)
b) Min Cost Path (GeeksForGeeks) – https://www.geeksforgeeks.org/min-cost-path-dp-6/
a) The values you can make (Codeforces) – http://codeforces.com/problemset/problem/687/C
b) Coloring Trees (Codeforces) – https://codeforces.com/problemset/problem/711/C
This concludes our introduction to dynamic programming! We have read and understood the basics of dynamic programming. Soon, I shall post my own explanations of certain fundamental 1-dimensional and multi-dimensional dynamic programming problems.
Picture from:Business vector created by freepik – www.freepik.com