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

Each item triggers a choose-or-skip decision, and the state is everything you've accumulated so far — usually a sum or capacity. The 2-D table indexes items along one axis and the accumulated state along the other.

Problempartition into two equal-sum subsetsInput[1, 5, 11, 5]target11

items

112

sum →01234567891011

∅

+11

Total = 22, target = 11. Each dp[i][s] answers: "can we make sum s using the first i items?"

step

0 / 50

target

choice

—

answer

—

0 / 50

items

03 / The pattern signature

# knapsack — choose or skip per itemdp[0][0] ← base case (often true / 0)for i in 1..n:for s in 0..target:skip ← dp[i−1][s]take ← if s ≥ w[i]: dp[i−1][s−w[i]] else falsedp[i][s] ← combine(skip, take)return dp[n][target]# subset sum: combine = OR; 0/1 knapsack: combine = max# unbounded (coin change): read dp[i][s−w] instead of dp[i−1][s−w]

04 / When to recognize this pattern

"pick a subset"

The problem asks whether some subset of the items satisfies a constraint, or which subset is optimal under a budget. If the order of items doesn't matter, suspect knapsack.

"weight / capacity / target"

A numeric budget (capacity, sum, count) gates the choices. The budget becomes the second axis of your DP table.

"each item is unique"

Standard 0/1 knapsack: each item can be taken at most once. If items are reusable, you're in unbounded knapsack territory (coin change) — the recurrence reads from the current row instead of the previous one.

"the state has two axes"

(items processed, sum so far) or (items processed, capacity used). When the natural state has more than two axes, the family bends — but the choose/skip skeleton survives.

05 / Common pitfalls

Confusing 0/1 with unbounded.

0/1 knapsack reads from dp[i-1][s-w] (the previous row) — each item used at most once. Unbounded reads from dp[i][s-w] (the current row) — items can repeat. When compressed to a 1-D array, 0/1 sweeps right-to-left; unbounded sweeps left-to-right. Get this backwards and the table silently produces wrong answers.

ii.

Forgetting to short-circuit on odd totals.

Partition-equal-subset-sum requires the total to be even — odd totals are immediately impossible. Catching this before the DP runs saves O(N · S) work in half of the inputs.

iii.

Pseudo-polynomial complexity surprises.

The runtime is O(N · S) where S is a numeric target — not log the target. Inputs with small N but huge sums (e.g., [10^9]) make knapsack DP infeasible. Spot this and switch to a different approach (meet-in-the-middle, branch-and-bound).

06 / Go practice — on LeetCode

Four problems across the knapsack family. The first three vary the combine rule (OR, count, max). The fourth shifts to unbounded — same skeleton, current-row reads.

01Partition Equal Subset Sum— LC 416medium→02Target Sum— LC 494medium→03Ones and Zeroes— LC 474medium→04Coin Change— LC 322medium→

— / 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