## Dynamic Programming

### What is Dynamic Programming? When and How to apply Dynamic Programming?

Dynamic Programming (DP) is an algorithmic paradigm that solves a given complex problem by

• breaking it into sub-problems
• and storing the results of sub-problems 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)
StateState Transition relation is difficult to thinkState transition relation is easy to think
CodeCode gets complicated when lot of conditions are requiredCode is easy and less complicated
SpeedFast, as we directly access previous states from the tableSlow due to lot of recursive calls and return statements
Subproblem solvingIf all subproblems must be solved at least once, a bottom-up dynamic-programming algorithm usually outperforms a top-down memoized algorithm by a constant factorIf 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 EntriesIn Tabulated version, starting from the first entry, all entries are filled one by oneUnlike 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)