Dynamic Programming is mainly an optimization over plain recursion. Wherever we see a recursive solution that has repeated calls for same inputs, we can optimize it using Dynamic Programming.
The idea of solving any problem using Dynamic Programming is to divide a problem into 'overlapping' subproblems and then reconstructing the solution using these subproblems.
| Greedy Algorithm | Dynamic Programming |
|---|---|
| Immediate best solution | Optimal best solution |
| Sometimes gives optimal solution | Always gives optimal solution |
| Subproblems are not depended | Subproblems are interdepended |
| Faster runtime | Slower runtime |
1. Matrix Chain Multiplication
5. Weighted Interval Scheduling
6. Longest Increasing Subsequence