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.

## Pre-Requisites

To apply DP, a problem must have:

**Overlapping Sub-problems**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.

**Optimal Sub-structure**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

`t`

to some ending period`T`

, one implicitly has to solve sub-problems starting from later dates`s`

, where`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

State is a set of parameters which will tell the certain position or standing in the given problem.

### Workflow

- 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)