Dynamic programming is an optimization of Divide-and-Conquer Paradigm.
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.
An algorithmic problem can be solved with a DP approach if a recurrence relation can be identified, and it is known that the sub-problems overlap. A way to check for overlapping can be to use a recursion tree to show the recursive function calls, and look for any common calls.
The criteria for a solution to be considered a DP solution is:
- Breaking down problems into sub-problems
- Solutions of sub-problems are overlapping i.e. a sub-solution can solve/aid in solving multiple sub-problems.
In most cases, DP is used to solve optimisation problems.
Memoization
Memoization is the process of storing solutions of sub-problems, such that they can be looked up for future sub-problems. It is considered a ‘bottom-up’ approach, since sub-problems of minimal sizes are cached first.
- Bellman-Ford Algorithm
- Dijkstra’s Algorithm
- Fibonacci Algorithm
- Floyd-Warshall’s Algorithm
- Warshall’s Algorithm