Dynamic Programming
01 / The shared mechanism
A table fills itself, one cell at a time — each entry composed from a constant number of earlier ones. The recurrence changes per sub-pattern, but the machinery — state, transition, fill order — is shared.
01 / The one-sentence essence
Each cell of a 1-D table answers a smaller version of the same problem — fill it once, in order, and the answer at any position composes from a constant number of earlier cells.
Problemmax loot from non-adjacent housesInput[2, 7, 9, 3, 1, 8]
input
20
71
92
33
14
85
dp
?0
?1
?2
?3
?4
?5
Each dp[i] is the max loot considering houses 0..i. Fill left to right.
step
0 / 7
i
—
choice
—
max so far
0
0 / 7
02 / The pattern signature
# 1-D DP — pick one of two options at each stepdp[0] ← base case 0dp[1] ← base case 1for i in 2..n−1:dp[i] ← f(dp[i−1], dp[i−2], input[i])return dp[n−1]# house robber: f = max(dp[i−1], dp[i−2] + nums[i])# max subarray (Kadane): f = max(nums[i], dp[i−1] + nums[i])# climbing stairs: f = dp[i−1] + dp[i−2]
03 / When to recognize this pattern
"max / min / count of"
You're optimizing or counting, and the answer at position
i can be composed from answers at smaller positions. If brute-forcing is exponential, suspect DP."non-adjacent / sequence"
A positional constraint — can't pick neighbors, must keep order, must form a subsequence. The choice at each step interacts with earlier choices.
"overlapping subproblems"
A naive recursion would solve the same smaller problem many times. DP caches.
"optimal substructure"
The optimal answer at
i uses optimal answers at smaller indices — not just any answers. Without this, greedy is the wrong tool but DP can't help either.04 / Common pitfalls
i.
Getting the base cases wrong.
dp[0] and dp[1] are where most off-by-ones live. Read them out loud: "the answer if I only have one element" / "the answer if I have two elements". Sanity-check with the smallest non-trivial inputs before writing the loop.ii.
Iterating in the wrong direction.
The recurrence dictates the fill order — you can't read
dp[i+1] before it's written. Left-to-right is the default, but some problems (e.g., rod-cutting's dual form) need right-to-left.iii.
Reaching for greedy when DP is needed.
If a local-optimal choice at each step can lock you out of a better global answer (e.g., "rob this small house now" prevents "rob the big house two ahead"), greedy will fail. DP considers both branches and takes the max.
05 / Go practice — on LeetCode
Four problems, ordered by where each one's recurrence is. The first three are 1-D linear DP; the fourth lifts you into O(N²) DP — still a 1-D table, just a wider dependency.
— / When to use which
1-D linear
Use when the answer at index i depends on a constant number of earlier indices.
house-robber · climbing-stairs · max-subarray
2-D grid
Use when the state has two indices — a grid, or two interacting sequences.
min-path · LCS · edit-distance
knapsack
Use when each item triggers a choose-or-skip decision under a capacity constraint.
subset-sum · coin-change · partition
interval
Use when the state is a range
(i, j) and the answer composes from inner intervals.palindrome · matrix-chain · burst-balloons
state machine
Use when each index can be in one of several finite states with rules for transitioning between them.
stock · cooldown · two-state