Dynamic Programming
The two common dynamic programming approaches are:
Memoization: Known as the “top-down” dynamic programming, usually the problem is
solved in the direction of the main problem to the base cases.
Tabulation: Known as the “bottom-up '' dynamic programming, usually the problem is
solved in the direction of solving the base cases to the main problem
Note: The base case does not always mean smaller input. It depends upon the
implementation of the algorithm.
When we see a problem, it is very important to identify it as a dynamic programming
problem. Generally (but not limited to) if the problem statement asks for the following:
Count the total number of ways
Given multiple ways of doing a task, which way will give the minimum or the
maximum output.
We can try to apply recursion. Once we get the recursive solution, we can go ahead to
convert it to a dynamic programming one.
Once the problem has been identified, the following three steps comes handy in
solving the problem:
Try to represent the problem in terms of indexes.
Try all possible choices/ways at every index according to the problem statement.
If the question states
Count all the ways - return sum of all choices/ways.
Find maximum/minimum- return the choice/way with maximum/minimum output.