Dynamic programming is an optimization of Divide-and-Conquer.
Similar to divide-and-conquer, dynamic programming algorithms split the problem into related sub-problems. Solutions to sub-problems can be used in other to sub-problems. In this way, the final solution is created by ‘building’ on to subproblems.
One method to do is known as Memoization, where results of subproblems are stored for future use, in case the subproblem recurs.
- Dijkstra’s Algorithm
- Fibonacci Algorithm
- Floyd-Warshall’s Algorithm
- Knapsack Problem
- Transitive Closure Algorithm