Classic DP Patterns

Here’s the secret that makes DP tractable: there aren’t dozens of DP problems, there are about seven shapes, and almost every “new” problem is one of them wearing a costume. House Robber, Coin Change, Edit Distance, Longest Common Subsequence — once you can name the state signature on sight, the recurrence (and the code) writes itself. This page is the seven shapes and how to recognize each.

Seven shapes cover the overwhelming majority of DP interview problems. Once you’ve internalized these, most “new” problems are just one of these in a costume.

For each pattern we’ll give: the canonical problem, the state, the transition, the code, and a list of other problems that wear the same skin.

Pattern 1 — Linear (1D) DP

The simplest shape. State is a single index i. dp[i] depends on a constant number of earlier cells like dp[i - 1], dp[i - 2], or dp[i - k] for fixed k.

Canonical: House Robber

You can’t rob two adjacent houses. Maximize your loot from a row of houses with values nums[i].

State: dp[i] = max loot from the prefix nums[0..i]. Transition: at house i, either skip it (dp[i - 1]) or rob it and the best from before its neighbor (nums[i] + dp[i - 2]). Base: dp[0] = nums[0], dp[1] = max(nums[0], nums[1]).

Space-optimizable to O(1) — just keep prev1 and prev2. Classic linear DP signature.

Same skin

Climbing Stairs — dp[i] = dp[i-1] + dp[i-2].
Min Cost Climbing Stairs — dp[i] = cost[i] + min(dp[i-1], dp[i-2]).
Maximum Subarray (Kadane) — dp[i] = max(nums[i], nums[i] + dp[i-1]).
Decode Ways — dp[i] = dp[i-1] (if single-digit valid) + dp[i-2] (if two-digit valid).

Pattern 2 — Grid (2D) DP

State is a pair (i, j) — usually a position in a grid or two parallel strings. dp[i][j] depends on neighbors like dp[i-1][j], dp[i][j-1], dp[i-1][j-1].

Canonical: Unique Paths

Count distinct paths from (0, 0) to (m-1, n-1) in a grid, moving only right or down.

State: dp[i][j] = number of paths to cell (i, j). Transition: dp[i][j] = dp[i - 1][j] + dp[i][j - 1]. Base: the entire first row and first column are 1 (only one way to reach them).

Space-optimizable to O(n) — only the previous row is needed.

Same skin

Unique Paths II (with obstacles) — same transition, plus dp[i][j] = 0 on blocked cells.
Minimum Path Sum — dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]).
Maximal Square — dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) if grid[i][j] == 1.
Triangle min path sum — same shape on a triangle grid.

Pattern 3 — 0/1 Knapsack

You have items, each with a weight and a value. You have a capacity. Pick a subset that maximizes value under the capacity constraint. Each item can be picked at most once.

State: dp[i][w] = max value using the first i items with capacity w. Transition: at item i, either skip it (dp[i - 1][w]) or take it (dp[i - 1][w - weight[i]] + value[i], if it fits). Base: dp[0][w] = 0 (no items → no value, any capacity).

Time: O(n × W). Space: O(n × W), optimizable to O(W) by iterating capacity in reverse (so we don’t double-count an item taken in the current row):

Predict first

The space-optimized 0/1 knapsack iterates capacity w in REVERSE (from W down to weight[i]). What breaks if you iterate forward instead?

dp = [0] * (W + 1)
for i in range(n):
    for w in range(W, weight[i] - 1, -1):     # reverse — critical
        dp[w] = max(dp[w], dp[w - weight[i]] + value[i])

The reverse loop is the most common knapsack interview gotcha. Iterating forward turns 0/1 knapsack into unbounded knapsack — a different problem.

Same skin

Partition Equal Subset Sum — knapsack where capacity = sum / 2 and values = weights; ask “can we hit exactly that capacity?”
Target Sum — assign + or - to each number to hit a target; reduces to a subset-sum DP.
Last Stone Weight II — minimize |sum_A - sum_B|; reduces to subset sum.
Ones and Zeroes — knapsack with two capacities (count of 0s and count of 1s).

Pattern 4 — Unbounded Knapsack

Same as 0/1 knapsack, but each item can be picked infinitely many times. The state is still dp[i][w], but in the recurrence the “take” branch comes from dp[i][w - weight[i]] instead of dp[i - 1][...] — because after taking item i, you’re allowed to take it again.

Canonical: Coin Change

Given coins of denominations coins[] and an amount n, what’s the minimum number of coins to make n? Return -1 if impossible.

State: dp[w] = min coins for amount w. Transition: dp[w] = min(dp[w - c] + 1) over all coins c <= w. Base: dp[0] = 0.

Time: O(n × amount). Space: O(amount) already, no further optimization needed.

Same skin

Coin Change II (count of ways, not min) — iterate coins outside and amount inside for “combinations”; flip for “permutations.”
Perfect Squares — coins are [1, 4, 9, 16, ...]; find min coins to sum to n.
Word Break — “coins” are dictionary words, “amount” is the string; can we tile it?
Combination Sum IV — count tilings allowing different orderings.

⚠️

Coin Change II vs Coin Change is the most common DP-loop-order trap. To count combinations (unordered), iterate coins in the outer loop and amount in the inner. To count permutations (ordered), do the reverse. Same recurrence, different loop order — different problem.

Pattern 5 — Longest Increasing Subsequence (LIS)

A subsequence is a sequence you get by deleting some elements without changing the order of the rest. LIS = the longest such subsequence that’s strictly increasing.

State: dp[i] = length of the LIS that ends at index i. Transition: dp[i] = 1 + max(dp[j]) for all j < i with nums[j] < nums[i]. If no such j exists, dp[i] = 1. Answer: max(dp[i]) over all i (the LIS doesn’t have to end at the last element).

Time: O(n²). Space: O(n).

There’s an O(n log n) LIS using a patience-sorting trick — maintain a list of “tail of best subsequence of each length” and binary-search the insertion point. We cover it in the practice problem. It’s worth knowing if the interviewer says “now do it faster.”

Same skin

Number of LIS — track count of LIS-of-max-length in addition to the length.
Russian Doll Envelopes — sort by width, then LIS on heights.
Longest Bitonic Subsequence — LIS from the left + LIS from the right.
Box Stacking — sort boxes by base, LIS by height with stackability check.

Pattern 6 — Longest Common Subsequence (LCS)

Two strings. Find the longest sequence of characters appearing in both, in order, but not necessarily contiguously.

State: dp[i][j] = length of LCS of s1[0..i-1] and s2[0..j-1]. Transition: if s1[i - 1] == s2[j - 1], dp[i][j] = dp[i - 1][j - 1] + 1. Else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]). Base: dp[0][j] = dp[i][0] = 0.

Time: O(n × m). Space: O(n × m), optimizable to O(m) by rolling on rows.

Recall the two transition lines — the whole LCS recurrence lives here:

python · fill in the blanks0/2 hints

def longest_common_subsequence(s1, s2):
  n, m = len(s1), len(s2)
  dp = [[0] * (m + 1) for _ in range(n + 1)]
  for i in range(1, n + 1):
      for j in range(1, m + 1):
          if s1[i - 1] == s2[j - 1]:
              # ??? match vs mismatch transition
          else:
              # ??? match vs mismatch transition
  return dp[n][m]

Same skin

Longest Common Substring — same but dp[i][j] resets to 0 on mismatch. The answer is max(dp[i][j]) everywhere, not dp[n][m].
Shortest Common Supersequence — n + m − LCS.
Distinct Subsequences — count, not length: dp[i][j] = dp[i-1][j-1] + dp[i-1][j] on match, else dp[i-1][j].
Longest Palindromic Subsequence — LCS of s with reverse(s).

Pattern 7 — Edit Distance

Two strings. Find the minimum number of single-character insertions, deletions, or replacements to turn s1 into s2. The Swiss army knife of string DP.

State: dp[i][j] = min edits to turn s1[0..i-1] into s2[0..j-1]. Transition: if s1[i - 1] == s2[j - 1], dp[i][j] = dp[i - 1][j - 1] (no edit needed). Otherwise, take 1 plus the minimum of:

dp[i - 1][j - 1] — replace
dp[i - 1][j] — delete from s1
dp[i][j - 1] — insert into s1 (equivalent to advancing in s2)

Base: dp[0][j] = j (insert j chars), dp[i][0] = i (delete i chars).

Time: O(n × m). Space: O(n × m), optimizable to O(m).

Same skin

One Edit Distance — early exit when count exceeds 1.
Delete Operation for Two Strings — n + m − 2 × LCS.
Minimum ASCII Delete Sum — same shape, but += ascii(char) instead of += 1.
Wildcard Matching / Regex Matching — same skin, * and ? extend the transition table.

The classification cheat sheet

Pattern	State signature	Hallmark recurrence ingredient	Time
1D linear	`dp[i]`	`dp[i-1]`, `dp[i-2]`	`O(n)`
2D grid	`dp[i][j]`	`dp[i-1][j]`, `dp[i][j-1]`	`O(n × m)`
0/1 knapsack	`dp[i][w]`	skip vs take (use `dp[i-1][...]`)	`O(n × W)`
Unbounded knapsack	`dp[w]`	`dp[w - coin]` (reuse current row)	`O(n × W)`
LIS	`dp[i]`	`max(dp[j]+1)` over `j < i`	`O(n²)` or `O(n log n)`
LCS	`dp[i][j]`	match: `dp[i-1][j-1]+1`; else max	`O(n × m)`
Edit distance	`dp[i][j]`	match: `dp[i-1][j-1]`; else `1 + min` of 3	`O(n × m)`

If a problem matches one of these state signatures and one of these recurrence ingredients, you’re already 80% done.

Quick check

You see: 'pick a subset of items with weights w[i] to maximize value, subject to total weight ≤ W'. Which pattern?

Coin Change asking for MINIMUM coins vs Coin Change II asking for COUNT of ways. What's the key difference in code?

What's the difference between Longest Common Substring and Longest Common Subsequence?

Seven shapes, and you can now name the state signature on sight. Next: advanced DP — bitmask DP, interval DP, DP on trees, and digit DP, for the problems whose state doesn’t fit the seven basic shapes.

Memoization vs Tabulation Advanced DP

Finished this page?