How to tell which dynamic programming pattern a problem wants

Updated July 31, 2026 · techinterview.org

Most dynamic programming problems in an interview fall into six or seven recognizable shapes. Once you can name the shape from the problem statement, the recurrence almost writes itself, and the part that used to feel like a flash of insight becomes filling in a template you have seen before.

What interviewers are testing is recognition. Can you see that “split this array into two halves with equal sums” runs on the same machinery as the 0/1 knapsack? That edit distance and longest common subsequence are the same table over two string prefixes with a different payoff in each cell? The families below cover the large majority of what shows up at Google, Amazon, Meta, and the trading firms, and the canonical problem in each row is the one I would hand someone who wants to drill that shape until it is automatic.

DP family	What a cell holds	Recurrence, in words	Canonical problems	Time / space
1D, decide per index	Best answer using the first i elements	dp[i] from dp[i-1] and dp[i-2]	House Robber, Climbing Stairs, Decode Ways, Word Break	O(n) / O(1)
0/1 knapsack and subset sum	Best value or reachability with the first i items at capacity w	dp[i][w] from dp[i-1][w] and dp[i-1][w – weight]	Partition Equal Subset Sum, Target Sum, 0/1 Knapsack	O(n·W) / O(W)
Unbounded knapsack	Best over amount a with items reusable	dp[a] from dp[a – item] at the same layer	Coin Change, Coin Change II, Combination Sum IV	O(n·A) / O(A)
Two-sequence table	Answer over the prefixes s[..i] and t[..j]	dp[i][j] from its diagonal, top, and left neighbors	Edit Distance, Longest Common Subsequence, Regex Matching	O(mn) / O(min(m, n))
Grid path	Best path that reaches cell (i, j)	dp[i][j] from the cells above and to the left	Unique Paths, Minimum Path Sum, Maximal Square	O(mn) / O(n)
Interval or range	Answer on the subarray from i to j	dp[i][j] from a split point k inside the range	Burst Balloons, Matrix Chain Multiplication, Min Cost to Cut a Stick	O(n³) / O(n²)
Increasing subsequence	Best subsequence ending at i, or a tails array	dp[i] = 1 + max(dp[j]) over earlier smaller j	Longest Increasing Subsequence, Russian Doll Envelopes, Number of LIS	O(n log n) / O(n)
State machine	Best value in each discrete state at step i	dp[i][state] from the legal prior states	Best Time to Buy and Sell Stock (cooldown and k-transaction variants), Paint House	O(n·k) / O(k)

When the answer only looks back a step or two

The simplest family is a single array where dp[i] is the best answer using the first i elements, and each entry depends on one or two earlier ones. House Robber is the textbook case: at every house you either skip it and keep the best total so far, or take it and add it to the best total from two houses back.

def rob(nums):
    prev, cur = 0, 0
    for n in nums:
        prev, cur = cur, max(cur, prev + n)
    return cur

There is no array at all in the final version. Once the recurrence only reaches back a fixed distance, you keep a couple of variables and drop the O(n) space. Interviewers push for exactly this after you get the table working, so have the rolling-variable version ready. Word Break lives in the same family with a twist: dp[i] is whether the first i characters can be segmented, and instead of looking back one step you look back over every dictionary word that could end at position i.

Knapsack is a family, not a single problem

The moment a problem asks you to pick a subset under a capacity or a target, you are in knapsack territory. The 0/1 version, where each item is used at most once, has state dp[i][w]: the best you can do considering the first i items with capacity w. Partition Equal Subset Sum is this in disguise, where the capacity is half the total sum and you are asking whether that target is reachable. Target Sum becomes the same thing once you rearrange the plus and minus assignments into a subset that has to hit a specific value.

The unbounded variant, where items repeat, collapses to one dimension. Coin Change asks for the fewest coins to make an amount, and because a coin can be reused, dp[a] depends on dp[a - coin] at the same layer rather than a previous row.

def coin_change(coins, amount):
    dp = [0] + [float('inf')] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

Greedy fails here for coin sets like [1, 3, 4] making 6, and a good interviewer will hand you exactly that set to see whether you reach for DP or hand-wave a greedy answer. Coin Change II swaps the question to counting combinations, which changes the loop order: iterate coins on the outside so you count each combination once instead of every ordering of it.

Two strings, one table

Any problem comparing two sequences builds a 2D table where dp[i][j] is the answer for the first i characters of one input against the first j of the other. Longest common subsequence is the anchor: if the current characters match, extend the diagonal, otherwise take the better of dropping one character from either side.

def lcs(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]

Edit Distance is the same grid with three moves priced into each mismatch, an insert, a delete, or a replace, and regular-expression and wildcard matching are the same idea with extra cases for the * character. If you can write LCS from memory, you can derive the rest at the whiteboard by asking what each cell’s neighbors mean.

Grids and intervals both fill a 2D table, but the loop order differs

Grid problems walk a matrix where each cell depends on the ones above and to the left, so a plain row-by-row sweep works. Minimum Path Sum, Unique Paths, and Maximal Square all fit: dp[i][j] combines the current cell with the best of its top and left neighbors. These reduce to a single row of memory because you only ever need the previous row.

Interval problems also fill a 2D table, but dp[i][j] covers a subarray from i to j and depends on shorter ranges inside it. That forces you to loop by increasing length rather than by index, and it is the detail people miss. Burst Balloons is the one that separates people who memorized templates from people who understand them. The natural instinct is to ask which balloon to pop first, and that gives a dependency you cannot resolve. Flip it and ask which balloon you pop last in a range, and the two sides become independent subproblems.

Longest increasing subsequence and its faster cousin

The O(n²) version is a 1D array where dp[i] is the length of the best increasing subsequence ending at index i, found by scanning every earlier element. The version interviewers want after that runs in O(n log n): keep a tails array where tails[k] is the smallest possible tail of an increasing subsequence of length k + 1, and binary-search each new number into place. Russian Doll Envelopes is LIS wearing a costume once you sort by width and run the subsequence logic on heights. Number of LIS asks you to carry a count alongside the length, a common way to make a familiar problem feel new.

When the answer depends on what you did last

State-machine DP shows up whenever you are in one of a few discrete conditions at each step and the moves between them are restricted. The stock-trading problems are the whole genre. With a cooldown after selling, you carry three running values: holding a share, having just sold, and resting.

def max_profit(prices):
    hold, sold, rest = float('-inf'), 0, 0
    for p in prices:
        prev_hold, prev_sold, prev_rest = hold, sold, rest
        hold = max(prev_hold, prev_rest - p)
        sold = prev_hold + p
        rest = max(prev_rest, prev_sold)
    return max(sold, rest)

Best Time to Buy and Sell Stock IV generalizes this to at most k transactions, which adds a k dimension and turns three variables into a small table indexed by transaction count and holding state. Paint House is the same skeleton with colors as the states and a no-two-adjacent constraint. Draw the states as boxes and the legal moves as arrows before you write anything, and the transitions fall out of the picture.

The hard part in every one of these is defining what a single cell means, not writing the loop. When you are stuck, name the smallest piece of the answer you can pin down and ask what it depends on. Depends on a fixed number of earlier cells, and it is 1D or a state machine. Depends on two prefixes, and it is a table. Depends on ranges inside itself, and you loop by length. Get the definition right and the code is almost an afterthought.