Dynamic Programming: Let’s make it layman simple.
You still scratching your head trying to understand Dynamic programming or more popularly termed as DP? DP is an absolute nightmare for some beginners and they start feeling that they will never be good enough to master it. The road to master DP is not all that different from the road to master any niche out there. The only way? PRACTICE!! AS MUCH AS YOU CAN!!!! I’m starting this DP series where I will be posting layman theory on Dynamic Programming and problems along with detailed solutions to DP. By the time I’m done, you will find yourself much more comfortable solving DP problems.
But seriously, what is Dynamic Programming??
Let me ask you a question. What is 8+2? 10. You must’ve answered very promptly and that too with good reason. It’s elementary stuff. But what if I ask, what is 1+2+3+2+2? Again 10. Was it again very prompt like the previous time? I don’t think so. Why is that? Because this time instead of having an 8, you had 1+2+3+2 which in turn adds to 8. Now think about what if you get 1+2+3+2 again somewhere? If you don’t memorise that this equals 8, won’t you have to calculate this again? You sure will have to. This is Dynamic Programming. Dynamic Programming is just a fancy way to say “Remember stuff to save time later”. But DP is not without trade offs. To remember stuff, we need space (memory) and we are trading space to save time. Some people also call DP as “Smart Brute force” and this will become more clear in the upcoming series.
How to know that we are dealing with a Dynamic programming problem??
If we are given a problem that can be broken down into smaller sub-problems and these can further be broken down into more smaller ones with some problems overlapping with the others, then that problems are DP problems.
Didn’t understand? Let’s take an example.
You have to find the sum to 1+2+3+2+1+2+3+2+4+2+2+5+2+2. Let’s denote this big addition as x. Note: Now we know that 1+2+3+2 is 8 :)
Our goal? Find the sum of x denoted as Sum(x).
Naive approach: Sum(x) = 33. How? Just add one by one until you reach the end.
Dynamic Programming approach: We can see some set of terms repeating so probably we can break it down into smaller sums?
1+2+3+2+1+2+3+2+4+2+2+5+2+2
Isn’t the highlighted part 8? We already calculated that before and saved it in the memory. Let’s move further.
1+2+3+2+1+2+3+2+4+2+2+5+2+2
This is 8, again. Let’s move further.
1+2+3+2+1+2+3+2+4+2+2+5+2+2
Well, 4 will be 4 so let’s continue.
1+2+3+2+1+2+3+2+4+2+2+5+2+2
So 2+2 will be 4. I don’t want to do this computation again so let me save this in the memory that 2+2 =4.
1+2+3+2+1+2+3+2+4+2+2+5+2+2
Can’t do much about 5 too. Let’s move ahead.
1+2+3+2+1+2+3+2+4+2+2+5+2+2
Oh I know this. This is 4. How? I saved it earlier.
So can we say that Sum(x) = Sum(1+2+3+2) + Sum(1+2+3+2)+Sum(4)+Sum(2+2)+Sum(5)+Sum(2+2)? Yes, I can.
Sum(x) = 8+8+4+4+5+4 implies Sum(x) = 33.
Do you now understand what are overlapping sub problems? Our problem was to find Sum(x). In order to solve Sum(x) we needed to calculate Sum(1+2+3+2)=8 , Sum(4)=4, Sum(5)=5 and Sum(2+2)=4. These are our sub problems while we also saw that some sub problems were overlapping ( Sum (1+2+3+2) and Sum(2+2)).
How did we make the choice of taking different amount of numbers in the above steps?
You might ask, why did we take 4 numbers in the start, then just 1 number and then 2 numbers? Who decides this? How did the author make this choice? It’s simple. I saw a pattern. I noticed that both 1+2+3+2 and 2+2 were repeating twice in our problem so it’s better to save the answers to these sub problems so that when I again come back to the same problem, I waste no time in calculating the same.
But what difference it would’ve made to do this with naive approach instead of DP?
Glad you asked. So in this case, not so much. It would’ve been easier to code with the naive approach here. The purpose of this example was to show how DP works and how it can save time. Let’s say that we had to add millions of numbers where each number is 6–7 digit long. Do you think a naive brute force would’ve worked? NO! IT WOULDN’T HAVE. That’s where you would’ve needed Dynamic Programming to save the day!
…
Thank you for reading! Let me know in the comments section if you want to read more about Dynamic programming and should I continue this series or not. If there are any other questions, or anything else you’d like to hear about, please don’t hesitate to put in a request.
