Dynamic Programming (DP) is an algorithmic paradigm that solves a given complex problem by
- breaking it into subproblems
- and storing the results of subproblems to avoid computing the same results again.
To apply DP, a problem must have:
If the problem can be broken down into sub-problems which are reused several times, or a recursive algorithm for the problem solves the same sub-problem over and over rather than always generating new sub-problems.
A naive recursive approach to such a problem generally fails due to an exponential complexity. If the problem also shares an optimal substructure property, dynamic programming is a good way to work it out.
If a problem has an optimal solution that can be constructed from optimal solutions of its sub-problems.
Typically, a greedy algorithm is used to solve a problem with optimal sub-structure if it can be proven by induction that this is optimal at each step. Otherwise, provided the problem exhibits overlapping sub-problems as well, dynamic programming is used.
To solve a dynamic optimization problem from some starting period
tto some ending period
T, one implicitly has to solve sub-problems starting from later dates
t < s < T.
Tabulation vs Memoization
|Tabulation (Bottom Up - DP)||Memoization (Top Down - Recursion)|
|State||State Transition relation is difficult to think||State transition relation is easy to think|
|Code||Code gets complicated when lot of conditions are required||Code is easy and less complicated|
|Speed||Fast, as we directly access previous states from the table||Slow due to lot of recursive calls and return statements|
|Subproblem solving||If all subproblems must be solved at least once, a bottom-up dynamic-programming algorithm usually outperforms a top-down memoized algorithm by a constant factor||If some subproblems in the subproblem space need not be solved at all, the memoized solution has the advantage of solving only those subproblems that are definitely required|
|Table Entries||In Tabulated version, starting from the first entry, all entries are filled one by one||Unlike the Tabulated version, all entries of the lookup table are not necessarily filled in Memoized version. The table is filled on demand.|
How to solve a DP problem
State is a set of parameters which will tell the certain position or standing in the given problem.
- Identify if it is a DP problem (how?)
- Decide the state
- Formulating relation among the states (states transition)
- Store states to optimize (Tabulation or Memoization)