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.
Pick a sub-pattern above. Each is independently linkable — start where the problem statement points.
↑ choose one— / 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