Dynamic Programming
External
- https://leetcode.com/discuss/study-guide/1490172/dynamic-programming-is-simple
- https://leetcode.com/discuss/study-guide/1508238/Dynamic-programming-is-simple-2
- https://leetcode.com/discuss/study-guide/1527916/Dynamic-programming-is-simple-3-(multi-root-recursion)
Internal
Overview
Refactor this to start with the idea that a dynamic programming problem is a recursive problem for which the same recursive calls (subproblems) get invoked unnecessarily many times. The most general underlying idea is to cache the results of those recursive calls in a (multidimensional, if necessary) array, where the array indices are given by the recursive call parameters, which must be integral and bound. Before making the call, look in the array, if the result is there, retrieve it in O(1) and use it, otherwise make the recursive all and on the way out, cache the result. Working example: the maximum profit problem resolved in playground L0714
Dynamic programming algorithms are optimized recursive algorithms, where we store the solution of smaller subproblems and use them in computing the solution for larger subproblems, avoiding duplicate work and yielding superior running times. The classic example where the difference between the straightforward recursive solution and the corresponding dynamic programming solution is obvious is computing Fibonacci numbers.
Dynamic programming solutions are recursive solutions, so it usually help to think about the recursive brute force approach first. The dynamic programming solution usually continue with an analysis of the optimal solution ("how would the optimal solution look like, and what happens if a specific element is part or is not part of the optimal solution"). The goal is to express the optimal solution as a recursive function of smaller subproblem solutions. The reasoning used for the optimal solution (n items) applies to an intermediary smaller subproblem of i size.
Once the recurrence expression is established for i, the algorithm proceeds by "brute force" computation of the smaller solutions starting with i = 1, and the selection of the optimal solution at step i by comparing results computed at previous steps and selecting the maximum. This "brute force" approach is feasible because the number of smaller solutions is asymptotically small, so it makes sense to compute them in an efficient running time.
The solution of the smaller subproblems is stored in a global array as the algorithm progresses. This technique is also called memoization. The semantics of storing the solution in the array is that the ith entry of the array is the solution of the ith subproblem. In a recursive call, if the smaller problem has been solved already (the array has a value), then that value is used. This is why it is crucial that we solve the subproblems in the right order, from smallest to largest. If the subproblem is not solved when we need it, the problem must be solved and the result stored. Once stored in the array, the subproblem solutions can be retrieved in O(1) later, to be used in computing the solution of larger problems.
The global array is unidimensional or bidimensional, depending on how many dimension the problem has. For example, the maximum weight independent set problem uses a unidimensional array, while the knapsack problem uses a bidimensional array.
The third step of the algorithm is executed after the final optimal solution is computed, and consists in backtracking the array of smaller solutions and establishing what input elements contributed to the optimal solution.
"Dynamic programming" is a term invented by Richard Bellman. Also see:
Canonical Use
- Computing Fibonacci numbers
- Maximum weight independent set problem
- The knapsack problem
- The sequence alignment problem
- Compute optimal binary search trees
- Distributed shortest path problem: Bellman-Ford Shortest-Path Algorithm