Dynamic programming
Table of Contents
Optimal substructure of the problem = optimal solution can be derived from the optimal solution of subproblems
- Bellman equation
Solves optimization problems that have overlapping subproblems
- based on recursive subproblems, that are computed repeatedly
- choose a path on which every computation is made only once (minimize the number of repeated computations)
- the problem is generally the runtime complexity as the correctness is almost free
- greedy algorithms are fast but require a lot of work to prove correctness
Dynamic Programming vs. Caching (Memoization) #
Caching
- top-down approach
- the recursion sets the way how to compute the subproblems
Dynamic Programming
- bottom-up approach
- programmer explicitly tells in which way the subproblems are solved in order to not computed already computed values
Sequence alignment, edit distance #
- we can compute edit distance in $O(mn)$ time and $O(m + n)$ space
- we do not care about the rows above the current row, only the previous ones
- we remember only the last row, the rest is discarded
- in contrast to memoization, dynamic programming allows me to do this, with memoization you can’t just say that you don’t have to remember something
- we can compute an optimal alignment in $O(mn)$ time and $O(m + n)$ space