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.
02 / The one-sentence essence
State has two indices, and the answer at (i, j) composes from a constant number of cells with strictly smaller coordinates — fill row by row so every dependency is already in the table when you reach it.Problemmin path sum top-left → bottom-rightGrid3×3
1?
3?
1?
1?
5?
1?
4?
2?
1?
Each dp[i][j] is the cheapest path from (0,0) to (i,j). Fill row by row.
step
0 / 10
cells filled
0
choice
—
min path sum
—
0 / 10
03 / The pattern signature
# 2-D DP — two indices, neighbor readsdp[0][0] ← base case# fill first row + first col cumulatively (1-D bases)for i in 1..R−1:for j in 1..C−1:dp[i][j] ← f(dp[i−1][j], dp[i][j−1], dp[i−1][j−1])return dp[R−1][C−1]# min path sum: f = grid[i][j] + min(top, left)# LCS: f = (s1[i]==s2[j]) ? diag+1 : max(top, left)# edit distance: f = (s1[i]==s2[j]) ? diag : 1 + min(top, left, diag)
04 / When to recognize this pattern
"grid"
The state is literally a grid coordinate — moves restricted to right/down is the classic shape. The dependency arrow is always backward, never sideways or upward.
"two sequences"
When the problem involves two strings or two arrays and asks about alignment, common structure, or transformation — LCS, edit distance, regex match. State
(i, j) = "first i of s1, first j of s2"."reads at most three neighbors"
Top, left, top-left diagonal. If you need to read a far-away cell, the DP is mis-formulated — you probably want a different state or different fill order.
"answer is at the corner"
The optimal solution lives at
dp[R−1][C−1] (or wherever the recurrence terminates). If the problem asks for the answer mid-table, you usually need to track the max over the table instead.05 / Common pitfalls
i.
Fill order that violates dependency direction.
The recurrence dictates which cells must be written before which. If
dp[i][j] reads from top and left, the standard row-by-row left-to-right sweep works. For palindrome substring DP, length-of-interval order is required instead. Always ask: where are my dependencies in the table relative to where I am?ii.
Indexing the input vs the table by 1.
When the table is sized
(M+1) × (N+1) (common for two-sequence DPs), the input indices and table indices are off by one. Misaligned by-one bugs are the bulk of time spent debugging.iii.
Forgetting the rolling-row optimization is reversible.
Compressing to a single row drops space from
O(R·C) to O(C), but you lose the path — only the final cost survives. If the problem also asks for the actual path (e.g., the path of cells in min-path-sum, or the LCS string itself), keep the full table.06 / Go practice — on LeetCode
Four problems, ordered by how the 2-D table is set up. The first two are literal grids; the next two are two-sequence DPs where the grid is conceptual — rows are positions in one string, columns are positions in the other.
— / 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