# Data Structures Algorithms
All Data Structures Algorithms notes →10 — Bitmask DP
DP whose state is a bitmask over which of n items are already accounted for — worked through the Traveling Salesman Problem and the Assignment Problem — plus the harder skill of recognizing when a subset, not an index or a range, is the axis a problem actually needs.
11 — Tree DP
DP where the state is anchored to a tree node instead of an index, the recurrence combines children's answers in a single postorder pass, and the tree's own shape — not an explicit table — supplies the fill order, worked through diameter of a binary tree and maximum independent set on a tree, both O(n), with re-rooting named as the harder next step.
12 — Interval DP
The matrix-chain-multiplication template — range state, increasing-length fill order, every split point tried — generalized to palindrome partitioning's nested interval DP and burst balloons' burst-last reframing, closing on the O(n³) ceiling that sets this family apart from cheaper 1D DP shapes.
8 — Matrix Chain Multiplication
Matrix chain multiplication's split-point recurrence derived from a hand-computed cost blowup across three parenthesizations of the same product, dp[i][j] defined over a RANGE for the first time in this book, the fill-by-increasing-interval-length rule a row-major sweep can't satisfy, and the O(n³) table traced end to end as the template this book's interval DP chapter generalizes.
9 — Digit DP
Counting integers in a range by their digit sum, forbidden digits, or repeats without enumerating them one at a time — building N's digits left to right under a tight/bound flag that is the one genuinely new state dimension this technique adds, worked top-down with a hand trace and a complexity argument for why the cost depends on N's digit count, not N itself.
1 — DP Fundamentals
Overlapping subproblems and optimal substructure defined precisely and shown to be independent properties, naive Fibonacci's recursion tree counted exactly with a call-counter to make the states-versus-total-calls gap numeric rather than asserted, why state definition — not the recurrence — is the actual design decision, and memoization vs. tabulation named as the two standard ways to implement any DP recurrence.
2 — Memoization
Top-down dynamic programming: caching each recursive call's answer to turn Fibonacci's O(2^n) blowup into O(n), deriving the cache's time/space cost and its recursion-depth limit, learning to define a state and its transition from scratch via Climbing Stairs, previewing tuple-keyed multi-dimensional caches, and weighing memoization against tabulation.
3 — Tabulation
Bottom-up tabulation on Fibonacci and 2D Unique Paths, the dependency-order rule that makes a fill loop valid, the rolling-array space optimization it enables, and where it beats memoization.
4 — Knapsack Problems
0/1 knapsack's two-dimensional state and transition, derived and traced on a worked table with item reconstruction, the 1D rolling-array collapse where iteration direction over capacity is the entire difference between 0/1 and unbounded knapsack, and the subset-sum / partition-equal-subset-sum problems that specialize the same transition.
5 — Longest Increasing Subsequence
The O(n²) DP with full state/transition derivation and predecessor-based reconstruction, the O(n log n) patience-sorting reformulation built directly on bisect_left, a proof sketch for why the tails array stays sorted, and when the quadratic version's easy reconstruction is worth trading away for the logarithmic version's speed.
6 — Longest Common Subsequence
Longest Common Subsequence's two-string 2D state and transition, traced on a full table for a worked example (ABCBDAB / BDCABA, LCS length 4) with backward reconstruction of the actual subsequence, the rolling-array space optimization's tension with reconstruction (Hirschberg's algorithm named, not derived), and the family of alignment problems — edit distance, longest common substring, shortest common supersequence — this same 2D shape generalizes to.
7 — Edit Distance
Edit distance's three-way insert/delete/replace transition derived directly from LCS's two-way match/skip transition, traced on a full 2D table and backward-reconstructed into an actual operation sequence, then set side by side with LCS to show precisely why replace has no LCS equivalent.