Dynamic Programming
DP organized by state shape — Linear, 2D Grid, Knapsack, Intervals, Tree DP, Bitmask.
DP isn't one technique — it's a family of techniques sharing a single insight: overlapping subproblems + optimal substructure → memoize. Splitting DP by state shape (1D? 2D? on a tree? on a bitmask?) makes it teachable. Lump them together and DP is mysticism.
Six pages, in roughly the order you should learn them:
DP — Linear / 1D
dp[i] from constant previous indices. Climbing Stairs, House Robber, LIS, Decode Ways.
DP — 2D Grid / Two-Sequence
dp[i][j] over a matrix or pair of sequences. LCS, edit distance, min path sum.
DP — Knapsack Family
0/1, unbounded, subset-sum, coin change, partition equal subsets.
DP — Intervals / Partition / MCM
dp[i][j] by trying every split k. Burst balloons, palindrome partitioning.
DP — Tree DP
Post-order DP where child results compose into parent. Diameter, house robber III.
DP — Bitmask
Use bits as set-of-used. dp[mask] over 2^n states. TSP, assignment.
How to think about a DP problem
The state shape is the question. Once you know the state shape, the transition usually writes itself.
Finished reading?
Mark it done to track your progress in Interview.
Cyclic Sort
For arrays containing integers in the range 1..n (or 0..n-1), place each value at its index by swapping. O(n) time, O(1) extra space.
DP — Linear / 1D
dp[i] depends on a constant number of previous indices. The foundation of dynamic programming — climbing stairs, house robber, longest increasing subsequence, decode ways.