Dynamic Programming Overview

Dynamic programming stores solutions to subproblems (table or memoization) when there is an optimal substructure and overlapping subproblems.

It is the counterpart to naive branching recursion with redundant work.

Overlapping subproblems: House Robber [1].

$$V(s)=\max_a\bigl(c(s,a)+V(s^{\prime})\bigr)$$

Where used

Knapsack, Edit Distance, Parsing, Routing with overlap, many ML decoding pre-steps. Memoization is the bridge from branching recursion.

Depth

Dynamic programming stores results of small states that are needed multiple times in the solution of larger states. Top-down memoization follows natural recursion and computes only reached states. Bottom-up tabulation establishes an order in which all dependencies are already present.

The most important modeling work is the state definition. It must contain enough information for future decisions but avoid redundant history. Transition, base values, and evaluation order come from this definition.

Difficulty levels

1. Recognize recurring states in a recursion tree.
2. Formulate the state and transition of a small optimization problem.
3. Reduce memory to a few lines through dependency analysis.

Pitfalls

Memoization of an incomplete key mixes different situations. In bottom-up methods, an incorrect filling order leads to transitions accessing yet uncalculated values.