Dynamic Programming — patterns and use cases

Under contest pressure you need fast signals. A problem is probably DP when you see any of these:

Question words:

• "In how many ways…" → counting DP.
• "Maximum / minimum / longest / shortest / cheapest…" subject to choices → optimisation DP.
• "Is it possible to reach / make / partition…" → feasibility (boolean) DP.

Structural signals:

• At each step you make a choice (take/skip an item, step 1 or 2, cut here or there), and choices made now affect what's available later.
• A greedy approach gives wrong answers on small cases — local best ≠ global best.
• The brute force is exponential (try all subsets / sequences), and you notice the same sub-situations recurring.
• The constraints are small enough for a polynomial table: n ≤ a few thousand for O(n²), n·W ≤ ~10⁸ for knapsack, etc.

The litmus test: "Can I describe the situation after some decisions with a small number of integers, such that the remaining problem depends only on those integers — not on how I got there?" If yes, those integers are the arguments of your recursive function — your state — and you have a DP.

Shape: f(i) depends on a constant number of nearby states (f(i-1), f(i-2), …). The state is a single index walking the array or a count.

Use when: the problem is over a sequence and each position's answer is built from a few neighbouring positions.

Recurrence template:

Canonical members: Fibonacci, climbing stairs, house robber (rob(i) = max(rob(i+1), a[i] + rob(i+2))), max subarray / Kadane (best(i) = max(a[i], best(i-1) + a[i])), counting tilings, decode-ways.

Example — house robber (max sum, no two adjacent), top-down:

The memo is a single array of size n; each rob(i) is computed once and reused.

Shape: process items one at a time; for each, you either include it or you don't, and the two branches lead to different remaining subproblems. State = "index of the item I'm deciding on (plus whatever resource it consumes)."

Use when: "choose a subset of these items to optimise X subject to a constraint." This is the backbone of subset-sum, partition, and the entire knapsack family.

Recurrence template:

Example — subset sum: can we pick a subset of a summing to S?

The take/skip structure is so common that recognising it instantly is half the battle. Knapsack is just this pattern with a value to maximise.

Knapsack is the most important rudimentary DP family. Three flavours, all built on pick-or-skip — and in top-down form the difference between them is which index the take branch recurses on.

0/1 knapsack — each item usable at most once. solve(i, cap) = best value from items i..n-1 with capacity cap. The take branch advances to i+1:

Unbounded knapsack / coin change — each item usable unlimited times. Identical code, except the take branch recurses on i (the same item stays available):

Bounded knapsack — each item available a fixed number of times (handled by splitting into powers of two — that's Part 2 territory).

Remember the rule: in top-down, i+1 = 0/1, i = unbounded. (Bottom-up encodes the same distinction as iterating capacity downward vs. upward — same idea, harder to get right. See the Tips topic.)

Shape: a 2D state where paths(i, j) depends on neighbouring cells — typically the cell above and/or to the left.

Use when: moving through a grid/matrix with restricted moves (right/down), or any problem naturally indexed by two coordinates.

Recurrence template (unique paths, moving only right or down):

Example — count paths from top-left to bottom-right (right/down only), top-down:

Variations you'll meet: minimum-cost path (cost[i][j] + min(paths above, left) instead of summing counts), paths with obstacles (return 0 on blocked cells), grids where you may also move diagonally. With memoization you never reason about fill order — the recursion pulls each dependency on demand.

Shape: state = "the answer pinned to ending at index i." The transition scans earlier indices.

Use when: longest/largest subsequence problems where order matters — LIS, longest chain, max-sum increasing subsequence.

Example — Longest Increasing Subsequence (basic O(n²)), top-down:

The pivotal modelling choice is "ending at index i." It makes the transition local: to extend, look back at every j < i with a[j] < a[i]. Two-sequence prefix DP (LCS, edit distance) generalises this to solve(i, j) over two prefixes — that's the Advanced chapter, but it grows directly out of this pattern.

When you're stuck, run this procedure explicitly:

1. Write the brute force as a recursion. "At each step I choose X; the rest is a smaller version of the same problem." Identify the parameters of that recursive function.

2. The parameters are your state. If solve(i, cap) fully determines the answer, then memo[i][cap] is your cache. Drop any parameter the answer doesn't actually depend on.

3. Minimise the state. Fewer dimensions = smaller memo = faster. Ask: "Does the answer really depend on this, or only on a summary of it?" (e.g. you may only need the sum so far, not the exact items chosen.)

4. Write the transition as the choices available from solve(state), each recursing on a strictly smaller sub-state.

5. Find the base cases — the states where the answer is immediate (empty suffix i == n, zero capacity, reached the target).

6. Locate the answer — which call is the original problem? Usually solve(0, full).

Golden rule: a correct state has the Markov property — given the state, the future is independent of how you arrived. If two different histories reach the same state, they must have the same set of futures. If not, your state is missing a dimension.

Before coding, check the DP will fit the limits. A judge does roughly 10⁸–10⁹ simple operations per second. Read the constraints and back-calculate. With memoization, total time ≈ (number of distinct states) × (work per call).

Memory matters too — and for top-down it's the memo that dominates. A memo[5005][5005] of int is ~100 MB — risky; a long long version is ~200 MB and likely MLE. Shrink it by minimising state dimensions before reaching for anything fancier. (Bottom-up additionally allows rolling-row tricks that top-down can't easily match — one reason to convert a memory-tight DP to iteration.)

Watch the recursion depth too. Top-down recurses as deep as the longest dependency chain — n for linear DP. Near n ≈ 10⁶ the call stack (~1 MB) can overflow; convert that one to bottom-up.