• i. DP Foundations: A DP is a shortest/longest path or a sum over paths in an acyclic state graph.
• ii. Knapsack and Subset Sum: Items with cost $w_i$ and value $v_i$, capacity $W$.
• iii. Classic DP Problems: The classic problems are worth knowing less for themselves than for the patterns they introduce:
• iv. LIS, LCS and Edit Distance: Three DPs on sequences with a lot of structure:
• v. Interval DP: State = a contiguous range $[l,r)$.
• vi. Bitmask DP: The state contains a subset of a small ground set ($n\le 20$–$23$), stored as an integer.
• vii. Broken Profile DP: DP over a grid with one small dimension $m$ (up to 10–20), where the state is the boundary between processed and unprocessed cells.
• viii. Digit DP: Count (or sum, or optimise) over integers in $[L,R]$ (up to $10^{18}$ or given as strings of $10^5$ digits) satisfying a property computed digit by digit.
• ix. Tree DP and Rerooting: State = a subtree (plus a few flags about its root).
• x. Dynamic DP: If a DP’s transition from the previous state is linear in a semiring ($(+,\times )$, $(\max ,+)$, $(\min ,+)$, $(\vee ,\wedge )$), then the DP is a product of small matrices, and a segment tree over the mat
• xi. DAG and Expected-Value DP: Every DP is a computation over a DAG of states.
• xii. Counting DP Techniques: Techniques for counting objects (mod a prime) where a direct DP would need too much state.
• xiii. Matrix Exponentiation DP: If the state vector evolves by a fixed linear map, $v_{i+1}=M{v}_i$, then $v_n=M^n{v}_0$ and $n$ up to $10^{18}$ costs $O(k^3\log n)$ for $k$ states.
• xiv. Convex Hull Trick: For transitions $d{p}_i={\min }_{j<i}(m_j{x}_i+c_j)+g(i)$, each earlier state is a line and the query is the lower envelope at $x_i$.
• xv. Divide and Conquer Optimization: For layered DPs $d{p}_t(j)={\min }_{k<j}(d{p}_{t-1}(k)+C(k,j))$ (“split the array into $t$ segments”), if the optimal $k$ is nondecreasing in $j$, compute one layer in $O(n\log n)$ by divide
• xvi. Knuth-Yao Optimization: Interval DPs $d{p}_{i,j}={\min }_{i<k<j}(d{p}_{i,k}+d{p}_{k,j})+w(i,j)$ run in $O(n^2)$ instead of $O(n^3)$ when the optimal split satisfies
• xvii. Monotone Queue, 1D1D and SMAWK: Three tools for $d{p}_i={\min }_j(d{p}_j+w(j,i))$:
• xviii. Aliens Trick: Also called WQS binary search or Lagrangian relaxation (IOI 2016 “Aliens”).
• xix. Slope Trick: When the DP state is a convex piecewise-linear function $f(x)$ with integer breakpoints, store it as its minimum value plus two heaps of breakpoints: