Mastering DP #1: Introduction to Dynamic Programming
Hey there! If you landed on this page to understand the concepts of dynamic programming then you have come a long way in your journey of problem-solving. Kudos to you!
Dynamic programming is one of the most confusing topics for most of the students preparing for interviews, including me. I've found some patterns during my preparation, So sharing them with you all. I guarantee if you stick by the entire series of articles with me, You'll be able to solve each and every question of Dynamic programming in your interview even if you are facing that question for the first time. Let's dive straight into the explanation.
2+2+2+2 = 8
Adding 2, 4 times gives us 8.
If I tell you to add two more to it.
2+2+2+2+2 = 10
Gives us 10. But how you calculated 10.
Did you add 2, 5 times from the start? OR Did you just add 2 to previously calculated 8, unconsciously. That gives us 10.
We usually compute the Fibonacci series using recursion.
We know that recursion works in a DFS manner and this approach will take 2n time but we can easily make an intuition that we are computing a lot of duplicate values.
Look closely in the entire tree only 6 values need to be computed and except that, the entire tree is duplicate.
Now we'll see how we can make intuition for any dynamic programming.
Optimal substructure: If a bigger problem solution can be constructed using the optimal solution of smaller subproblems.
Overlapping subproblem: Your problem is such that a lot of subproblems will have to be computed multiple times.
Memoize: Store a value when you compute it for the first time and use it later.
Memoization makes sense when the number of states that need to be computed is greater than the number of unique states. That will save a lot of time. We've already seen how to calculate the Fibonacci series using recursion. Now we see how we can take help of memoization.
You can see we are now calculating each Fibonacci series element once and then saving it to calculate further series.
For every DP problem, we have two ways to solve
Top-Down approach: Recursive+Memoization (Discussed above)
Bottom-up approach (Iterative): Start with the base case and everything computes a new state using the states you already have.
There is an extra requirement in the bottom-up approach. You need to know the order in which states will be computed. We must know, to calculate fib, we need f and f.
This is it for the introduction of dynamic programming. We'll gradually increase the complexity of questions and solve more problems in the Next parts of this series. I'm too lazy to develop a comment section below so you can throw your feedback on My LinkedIn profile.