VietMX Staff asked 3 years ago
Dynamic programming is an extension of Divide and Conquer paradigm.
- They both work by recursively breaking down a problem into two or more sub-problems. The solutions to the sub-problems are then combined to give a solution to the original problem.
- In Divide and conquer the sub-problems are independent of each other. Mergesort is a classic example of divide and conquer. The main difference between this example and the Fibonacci example is that in a mergesort, the division can (theoretically) be arbitrary, and no matter how you slice it up, you are still merging and sorting.
- In dynamic programming the sub-problem are not independent. So to calculate new Fib number you have to know two previous values. For Merge sort you don’t need to know the sorting order of previously sorted sub-array to sort another one.
- Dynamic programming approach may be applied to the problem only if the problem has certain restrictions or prerequisites:
- Optimal substructure — optimal solution can be constructed from optimal solutions of its subproblems
- Overlapping sub-problems — problem can be broken down into subproblems which are reused several times or a recursive algorithm for the problem solves the same subproblem over and over rather than always generating new subproblems.
- Dynamic programming approach extends divide and conquer approach with two techniques:
- memoization (top-down cache filling)
- tabulation (bottom-up cache filling)
