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.

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.

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

medium13

01Perfect Squares— LC 279→02Coin Change— LC 322→03Combination Sum IV— LC 377→04Partition Equal Subset Sum— LC 416→05Ones and Zeroes— LC 474→06Target Sum— LC 494→07Coin Change II— LC 518→08Minimum Cost For Tickets— LC 983→09Last Stone Weight II— LC 1049→10Longest Arithmetic Subsequence of Given Difference— LC 1218→11Toss Strange Coins— LC 1230→12Count Sorted Vowel Strings— LC 1641→13Minimize the Difference Between Target and Chosen Elements— LC 1981→

hard4

01Profitable Schemes— LC 879→02Tallest Billboard— LC 956→03Maximum Value of K Coins From Piles— LC 2218→04Painting the Walls— LC 2742→

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

tree DP

Use when the problem lives on a tree and each node's answer depends on its children's answers.

house-robber-III · diameter · max-path-sum

bitmask

Use when state is a subset of items (typically N ≤ 20) and only which items have been chosen matters — not the order.

assignment · TSP · sufficient-team