# 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