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 (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.

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