Algorithms · Cluster
Dynamic Programming
Optimal substructure, state design, and memoization.
- 01 Recurrences as DAGs: Why Optimal Substructure Makes Tables Work How a recurrence defines a graph of states, why overlapping subproblems collapse an exponential recursion tree into a polynomial one, and where the optimal-substructure argument fails.
- 02 Memoization Mechanics: Cache Keys, Laziness, and Recursion Depth How top-down memoization turns a recursion tree into a DAG, what the cache key must contain to be sound, and why the lazy traversal sometimes loses to a full table.
- 03 State Sufficiency: What the Past Must Leave Behind How to decide which facts about a partial solution a DP state must record, why insufficient states produce wrong answers rather than slow ones, and what each extra dimension costs.
- 04 Pseudo-Polynomial Knapsack: Why the Capacity State Is Not Polynomial The O(nW) knapsack table is polynomial in the capacity value and exponential in its bit length, which is why the problem stays NP-hard and why scaling the weights yields an approximation scheme.
- 05 Edit Distance and the Shape of a Two-Dimensional Table How the Levenshtein recurrence fills a grid, why three neighbouring cells are enough, and how the band and Hirschberg variants trade the full matrix for time and reconstruction ability.
- 06 Interval DP: Choosing the Last Operation Instead of the First Why splitting a contiguous range at its final split point turns exponential enumeration into an O(n cubed) table, and how the quadrangle inequality later removes a factor of n.
- 07 Longest Increasing Subsequence and the Tails Array Invariant The O(n log n) patience-sorting method keeps one number per length instead of a full two-dimensional table, and the invariant explaining why is a dominance argument.
- 08 Subset DP with Bitmask States: Held-Karp and the 2-to-the-n Wall Encoding a visited set as an integer makes the traveling-salesman recurrence exact in O(2^n n^2), and the same encoding supports submask enumeration and the sum-over-subsets transform.
- 09 Tree DP and Rerooting: Computing an Answer at Every Node Subtree DP evaluates a rooted tree in post-order, and a second top-down pass propagates the parent contribution so that every node gets the answer for the tree rooted at it.
- 10 Monotone Decision Points: Divide-and-Conquer Optimization in DP When the argmin of a one-dimensional recurrence is monotone in the state, the transition scan collapses from a factor of n to a logarithm, and the Monge condition is what licenses it.