Dynamic Programming

Dynamic programming is a technique which is used to optimize problems which are solved using recursion. 

A problem is solvable by using dynamic programming only if contains two essential properties :

1. Optimal Substructure: It means that the problem is solvable by combining solutions to the corresponding subproblems.
2. Overlapping Subproblems:  This means that if we solve the original problem using recursion, we will end up solving same subproblem multiple times. This leads to wastage of time and is one of the main basis of optimizations done in dynamic programming solution.