DPAlgorithmaka DP, dynamic optimization

Dynamic Programming

Solve a problem by defining subproblems whose answers are reused, so exponential recursion collapses to polynomial time.

▶ VisualizePattern: Dynamic ProgrammingPractice (11)
Progress

Overview

Dynamic programming (DP) is a method for problems that can be broken into subproblems that repeat. A naive recursion solves the same subproblem millions of times; DP solves each distinct subproblem once, stores the answer, and reuses it. The name is historical (Bellman, 1950s) and means nothing literal — think of it as "recursion with a lookup table".

Two properties must hold. Overlapping subproblems: the recursion tree contains the same node many times (Fibonacci computes fib(3) exponentially often). Optimal substructure: an optimal solution to the whole is built from optimal solutions to parts (the shortest path from A to C through B contains the shortest path from A to B). Without the first, DP gives no speedup over divide and conquer; without the second, a table of sub-answers cannot be combined into the right answer.

Every DP is fully specified by a single framework: State → Transition → Base case → Dependency order → Table → Optimization. The state names a subproblem with a small tuple of integers; the transition is a formula computing a state from smaller states; base cases anchor the recursion; the dependency order is a topological order of the implicit DAG of states; the table is where answers live; optimization means shrinking the table (often a 2D table to one or two rows) once the dependency structure is understood.

DP appears as its own topic family here — Memoization (Top-Down DP) and Tabulation (Bottom-Up DP) are the two execution styles, and 1D (Linear) DP, 2D (Two-Sequence) DP, Grid DP, Knapsack DP, Subsequence DP, Interval (Range) DP, State Machine DP, Tree DP, Bitmask DP, Digit DP and DP on DAGs are the shapes the state space takes in practice. Classic problems: Fibonacci Numbers, Climbing Stairs, House Robber, Coin Change, 0/1 Knapsack, Unbounded Knapsack, Longest Increasing Subsequence, Longest Common Subsequence, Edit Distance, Matrix Chain Multiplication, Kadane's Algorithm.

optimizationoverlapping subproblemsoptimal substructurememoizationtabulationstate

Intuition

A mental model before the formal terms.

Picture filling in a crossword where every clue is "add the two answers above me". Doing it by pure recursion means re-deriving the entire top of the grid each time you look at a cell. Writing answers into the grid as you go means each cell costs one addition, and the whole thing costs the number of cells.

Another picture: the recursion tree of fib(50) has about 2^50 nodes but only 51 distinct labels. Collapse every node with the same label into one and the tree becomes a small DAG with 51 vertices and 100 edges. DP is nothing more than evaluating that DAG once, in an order where every vertex's inputs are ready before it is.

The hard part of DP is never the code — a finished DP is three to ten lines. The hard part is choosing what to write on each cell: the state. A good state is the smallest description of "where am I" that still lets you decide the future without looking at the past.

How it works

  1. 1. State. Ask: "after making some decisions, what is the minimum information I need to finish optimally?" Encode it as a tuple of small integers, e.g. dp[i] = best answer using the first i items, dp[i][j] = answer for prefix i of A and prefix j of B, dp[mask][v] = answer having visited set mask, standing at v. The number of distinct states is the table size, which bounds your time.
  2. 2. Transition. Write the recurrence: how does dp[state] follow from strictly "smaller" states? Enumerate the last decision: "the last element is either taken or skipped", "the last cut is at position k", "the last character matches or not". dp[state] = best over choices of (cost of choice + dp[smaller state]).
  3. 3. Base cases. The states with no decisions left: dp[0] = 0, dp[i][0] = i, dp[1 << start][start] = 0. Also decide what "impossible" means (-inf, +inf, 0 ways, false) so that transitions from impossible states stay impossible.
  4. 4. Dependency order. The states form a DAG (transitions point to smaller states). Top-down Memoization (Top-Down DP) evaluates it lazily via recursion; bottom-up Tabulation (Bottom-Up DP) walks it in a topological order — increasing i, increasing interval length, increasing popcount of mask, post-order of a tree. If you cannot describe such an order, the state definition is circular and must be fixed.
  5. 5. Table. Allocate dp with a slot per state (array, 2D array, hash map for sparse states). Fill in dependency order. The answer is one cell (dp[n]), or an aggregate over cells (max over i of dp[i] for Longest Increasing Subsequence).
  6. 6. Optimization. If dp[i][*] depends only on dp[i-1][*], keep two rows (or one row iterated in the right direction, as in 0/1 Knapsack). If only a fixed window of earlier states matters, keep k variables. Monotonic-queue, convex-hull, divide-and-conquer and Knuth optimizations speed up specific transition shapes, but space reduction is the one you must always consider.

Why it works

Correctness follows from optimal substructure by induction over the dependency order: assuming every smaller state holds the true optimum, the transition considers every possible last decision and picks the best, so the current state also holds the true optimum. The base cases anchor the induction.

Efficiency follows from overlapping subproblems: total work = (number of states) × (work per transition). For Longest Common Subsequence that is n·m states × O(1) = O(nm), versus the 2^n leaves of the naive recursion. The exponential blowup existed only because the same states were recomputed.

The framework is the same for counting (replace max with sum), feasibility (replace max with OR), and optimization (max/min). Only the combining operator changes; states, transitions and order are identical. That is why one mental model covers "how many ways", "is it possible" and "what is the minimum cost".

Recognition

How to tell a problem wants this.

  • The question asks for "the number of ways", "the minimum cost / fewest steps", "the maximum value / longest length", or "is it possible to…" — and a greedy choice can be shown to fail with a small counterexample.
  • A brute-force recursion is easy to write but makes the same recursive call with the same arguments many times.
  • Decisions are made in sequence (left to right over an array, character by character, item by item) and the future depends on a small summary of the past (an index, a remaining capacity, the previous choice).
  • Constraint sizes are a strong hint: n ≤ 5000 suggests O(n²) states, n ≤ 500 with two sequences suggests O(n·m), n ≤ 20 suggests bitmask states O(2^n·n), n ≤ 100 intervals suggests O(n³), N ≤ 10^18 with a digit condition suggests Digit DP.
  • Keywords: "subsequence", "partition", "non-adjacent", "at most k transactions", "contiguous" (though contiguous max sum is Kadane's Algorithm), "minimum edits", "palindromic", "ways to tile/climb/decode".
“number of ways” → Dynamic Programming

Interactive visualization

Play, step, change the input. ← → and space work too.

Showing the closely related Fibonacci Numbers visualization.

Call stack (top first)
fib(6)
n=6
Recursion tree
fib(6)
memo
nfib(n)
1/23Call fib(6). Push a frame; the recursion tree grows one node.
Call in progressAnswered from memoReturned
PseudocodeLearn Fibonacci Numbers →
1fib(n):
2  if n <= 1: return n
3  if n in memo: return memo[n]
4  memo[n] = fib(n-1) + fib(n-2)
5  return memo[n]
Variables
n6
depth1
Complexity
best O(n)
avg O(n)
worst O(n)
space O(1)
Speed

Pseudocode

1# The DP framework, applied to "minimum coins to make amount A" (coin-change)
2# State:      dp[a] = fewest coins summing to a      (a in 0..A)
3# Transition: dp[a] = min over coins c <= a of 1 + dp[a - c]
4# Base:       dp[0] = 0; dp[a] = INF until proven reachable
5# Order:      increasing a (every a - c is smaller than a)
6# Table:      one array of size A + 1
7# Optimize:   nothing to shrink; the table already is one row
8dp = [INF] * (A + 1); dp[0] = 0
9for a in 1..A:
10  for c in coins:
11    if c <= a and dp[a - c] + 1 < dp[a]: dp[a] = dp[a - c] + 1
12return dp[A] if dp[A] != INF else -1

Implementations

1# Representative problem: minimum number of coins to make amount (coin change)
2# State: dp[a] = fewest coins summing to a. Transition: dp[a] = 1 + min(dp[a - c]).
3def min_coins(coins: list[int], amount: int) -> int:
41 · Table and sentinel
5    INF = float("inf")                  # inf + 1 == inf, comparisons stay correct
6    dp = [INF] * (amount + 1)
72 · Base case
8    dp[0] = 0                           # zero coins make amount 0
93 · Fill in dependency order
10    for a in range(1, amount + 1):      # every a - c < a is already final
114 · Transition over the last coin
12        for c in coins:
13            if c <= a and dp[a - c] + 1 < dp[a]:
14                dp[a] = dp[a - c] + 1
155 · Read the answer
16    return -1 if dp[amount] == INF else int(dp[amount])
17 
18 
19if __name__ == "__main__":
20    print(min_coins([1, 2, 5], 11))  # 3  (5 + 5 + 1)
21    print(min_coins([2], 3))         # -1
Walkthrough
  1. This is the representative example for the whole DP framework: state dp[a], transition over the last coin, base dp[0] = 0, increasing-a order, a one-row table.
  2. float("inf") is the sentinel; inf + 1 == inf and it compares greater than any int, so the min logic needs no guard.
  3. [INF] * (amount + 1) is fine for a 1D table because floats are immutable — the aliasing trap only bites with nested lists.
  4. range(1, amount + 1) visits amounts in increasing order; every dp[a - c] read is already final.
  5. int(dp[amount]) converts the float-typed cell back to an int for the caller.
Complexity (this implementation)
time O(amount × |coins|) · space O(amount)
Language notes
  • Python ints never overflow, so counting variants need no long long; only a modulus if the problem asks for one.
  • A list-of-floats table is slightly slower than ints; INF = amount + 1 (an int upper bound) is a common competitive trick.
  • This is the bottom-up form; functools.lru_cache gives the top-down form in two lines (see alternative).
Common mistakes in this language
  • Using 0 as the "unreachable" sentinel — dp[0] is legitimately 0 and the min test breaks.
  • Returning dp[amount] as a float (3.0) when an int is expected.
  • Iterating for a in range(amount) and losing the last cell.
Language differences that matter here
  • Sentinel for "unreachable": C++ needs a finite INF (1e9) small enough that INF + 1 does not overflow int; JS/TS and Python have a true Infinity / float("inf") that absorbs additions.
  • Counting variants overflow in C++ (int at 2^31, long long at 2^63) and lose precision in JS/TS beyond 2^53; Python ints are arbitrary precision.
  • Table allocation: std::vector<int>(n, INF) vs new Array(n).fill(INF) (a bare new Array(n) is sparse) vs [INF] * n.

Complexity

Best
—
Average
—
Worst
O(states × transition cost)
Space
O(states), often reducible to O(1 row)

Typical families: 1D O(n), two-sequence O(nm), interval O(n³), bitmask O(2^n·n²), tree O(n). The exponential naive recursion becomes polynomial because each state is evaluated once.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Optimization, counting or feasibility over sequential decisions where greedy fails and brute force repeats work.
  • The state space is small enough to enumerate: roughly ≤ 10^7–10^8 states × transition cost fits in a typical time limit.
  • The problem can be phrased as "best answer for a prefix / suffix / interval / subset / subtree".
Avoid it when
  • A greedy exchange argument holds (e.g. Activity Selection, Fractional Knapsack) — greedy is simpler and faster.
  • The state needs to remember an unbounded amount of history (the full set of visited items with n = 1000) — the table is too large; look for a different formulation or a different technique.
  • Subproblems do not overlap (merge sort, quick sort) — that is Divide and Conquer; a memo table adds cost without benefit.
  • The dependency graph has cycles (shortest paths with arbitrary weights) — use Dijkstra's Algorithm or Bellman-Ford rather than a DP table, or note that Bellman-Ford is DP over "number of edges used".

Alternatives

Divide and ConquerRecursion & BacktrackingActivity SelectionDijkstra's AlgorithmBellman-Ford
Compare: Greedy vs Dynamic Programming

Common mistakes

  • Wrong state — missing a dimension (forgetting "holding a stock or not" in stock problems, forgetting "which item index" in knapsack) so the transition silently depends on information the state does not carry.
  • Missing or wrong base case — dp[0] for "zero items" or "empty string" is usually 0, 1 (one way to make the empty selection), true, or INF; getting it wrong shifts every answer.
  • Wrong iteration order — reading dp[i-1][j] before it is written, or iterating capacity upward in 0/1 knapsack so an item is used twice.
  • Recomputing without a memo — a correct recurrence run as plain recursion is still exponential; the table is the whole point.
  • Using 0 as the sentinel for "impossible" when 0 is a legal value, so impossible states leak into real answers.
  • Integer overflow in counting DPs — take the modulus at every addition when the problem asks for mod 10^9+7.
  • Off-by-one between "first i items" (indices 0..i-1) and "item i"; be explicit which convention the state uses.

Interview patterns

Interview questions on this
Mock interviews

Example problems

Climbing StairseasyHouse RobbermediumCoin ChangemediumWord BreakmediumLongest Increasing SubsequencemediumLongest Common SubsequencemediumEdit DistancemediumPartition Equal Subset SummediumUnique PathsmediumBurst BalloonshardMaximum Subarraymedium