Dynamic Programming 101: Intuition and How to solving problems
Dynamic programming is really a beautiful concept that helps save computation time. Whenever a problem question is asked, it is actually difficult to come up with the dynamic programming solution the first time yourself and this is the reason why dynamic programming problems are fun puzzles because it allows one to find the pattern or the solution through creative thinking process.
Just for mental peace and validation, coming up with a dynamic programming solution for a problem that you see for the first time is difficult and if you are able to do it, Cheers!!! But if anyone out there is like me, who is unable to come up with solution then the other option is to practice a lot of dp problems. This gives a intuition and a pattern recognition whenever you face a new problem. So lets get this out of the way is the fact that: you should practice a lot of dp problems to understand and learn the pattern or recognize how and where dp is being applied.
The material is not a proved theory but more of a general practice steps to be followed. First way to realize whether a the problem has dp applicable is generally of 2 types of scenarios: if the problem asks for minimum/maximum cost or count number of ways.
Now there are 2 ways how a dp solution can be built: top-down approach or bottom-up approach. Top-down approach is also referred to as the memoization, which is nothing but starting with the larger problem, solving it, storing its result and then breaking the larger problem into the smaller problem. Now when solving the smaller problem, it is checked in the memorized table whether I have solved this problem or not.
Bottom-up approach is the exact opposite of top-down. Here, the solution is started from the base case, the results are stored and using the smaller sub-problem results we build towards the larger subproblem solutions.
In general bottom-up approach has a better performance than top-down as you need to start with smaller problem and therefore is able to compute faster.
Moving on, next question that comes to mind when solving through lot of leetcode dp problems whether a 2-D table is required or 1-D table. This parameter is determined through the recursive equation. The dp solution main crux lies in the recursive equation solution. To determine whether a dp table of 1D or 2D is required check the number of parameters that change when passing to the recursive equation function for solving the subproblems. If only a single variable/parameters changes for solving the subproblem then 1D table is sufficient, if 2 parameters change then 2D table, and so on.
There are scenarios where a 2D table can be made space optimized to 1D table but this requires certain constraints to be met which I might explain in another post on how to identify and optimize a 2D table into a 1D table which is applicable to limited number of problems.
To understand and develop the recursive equation solution, start with a basic recursive solution. Now, we can use dp definition of optimal substructure and overlapping subproblems. Optimal substructure in simple terms is nothing but if there exists a recursive equation/function then it is an optimal substructure. And to think in terms of coming up with a bottom-up solution think of base cases of the parameter for which you need to define/set values, which cannot be calculated before. Once you have got the base case values set and the equation, the table can be filled up and you have now successfully be able to come up and solve a dp problem.
Do let me know if this piece requires some examples to further explain and drive the concepts for more clarity. This information piece is long itself to read and adding the examples would make it much bigger and long pieces seem like a daunting task as they contain too much information. Hopefully this is able to guide and give you some tricks and techniques in tackling and handling dp problems when you are practicing.
