7 Dynamic Programming Patterns You Must Know (with Code)

Dynamic programming feels hard because people memorise solutions instead of a route — and the route never changes: write the brute-force recursion, name the state, cache it, and only then flatten it into a table. DP applies when a problem has optimal substructure (the answer is built from answers to subproblems) and overlapping subproblems (the same subproblem recurs). Spot those two, follow the route, and most "hard" DP questions collapse into one of seven families. The complete DSA patterns guide places DP against the other sixteen shapes; this is the interior of that one entry.

The route that actually works

1. Write the brute-force recursion. No caching, no table — just: to solve this, what smaller versions do I need? It will be exponential, and that is the honest statement of the problem.
2. Read the state off the recursion. The state is the set of arguments the function depends on. Write the recursion first and you never have to guess it.
3. Memoise. Cache on exactly those arguments. One line, usually, and it is where the exponential dies.
4. Convert to a table only if you need to — for space, for recursion depth, or because you were asked.

Candidates who start at step 4 usually cannot explain their own recurrence, and the interviewer finds out the moment they ask why a loop runs backwards. Start at step 1 and everything after it is a mechanical transformation of something you already justified out loud.

The whole route, on Coin Change: given denominations, return the fewest coins summing to a target, or −1 if impossible.

Stage 1 — the brute-force recursion

def coin_change(coins, amount):
    def fewest(rem):
        if rem == 0:
            return 0
        if rem < 0:
            return float('inf')          # this branch cannot pay for itself
        return min(fewest(rem - c) + 1 for c in coins)

    best = fewest(amount)
    return -1 if best == float('inf') else best

private static final int IMPOSSIBLE = Integer.MAX_VALUE;

public int coinChange(int[] coins, int amount) {
    int best = fewest(coins, amount);
    return best == IMPOSSIBLE ? -1 : best;
}

private int fewest(int[] coins, int rem) {
    if (rem == 0) return 0;
    if (rem < 0) return IMPOSSIBLE;
    int best = IMPOSSIBLE;
    for (int c : coins) {
        int sub = fewest(coins, rem - c);
        if (sub != IMPOSSIBLE) best = Math.min(best, sub + 1);
    }
    return best;
}

Exponential, and correct. Say both out loud before touching it.

Stage 2 — name the state, then memoise

The recursion depends on exactly one thing: rem, the amount still to pay. fewest(rem) = the fewest coins summing to exactly rem. One sentence, no ambiguity — the bar every state has to clear.

from functools import lru_cache

def coin_change(coins, amount):
    @lru_cache(maxsize=None)
    def fewest(rem):
        if rem == 0:
            return 0
        if rem < 0:
            return float('inf')
        return min(fewest(rem - c) + 1 for c in coins)

    best = fewest(amount)
    return -1 if best == float('inf') else best

public int coinChange(int[] coins, int amount) {
    int[] memo = new int[amount + 1];
    Arrays.fill(memo, -1);                  // -1 = not computed yet
    int best = fewest(coins, amount, memo);
    return best == IMPOSSIBLE ? -1 : best;
}

private int fewest(int[] coins, int rem, int[] memo) {
    if (rem == 0) return 0;
    if (rem < 0) return IMPOSSIBLE;
    if (memo[rem] != -1) return memo[rem];

    int best = IMPOSSIBLE;
    for (int c : coins) {
        int sub = fewest(coins, rem - c, memo);
        if (sub != IMPOSSIBLE) best = Math.min(best, sub + 1);
    }
    return memo[rem] = best;
}

The Python diff is one decorator. That is the point — the algorithmic work happened at stage 1.

Stage 3 — flatten it into a table

The recursion asks for smaller rem, so filling from 0 upward has every dependency ready.

def coin_change(coins, amount):
    INF = amount + 1                      # any real answer is at most `amount`
    dp = [INF] * (amount + 1)             # dp[rem] = fewest coins summing to rem
    dp[0] = 0
    for rem in range(1, amount + 1):
        for c in coins:
            if c <= rem:
                dp[rem] = min(dp[rem], dp[rem - c] + 1)
    return -1 if dp[amount] > amount else dp[amount]

public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);          // sentinel larger than any real answer
    dp[0] = 0;
    for (int rem = 1; rem <= amount; rem++) {
        for (int c : coins) {
            if (c <= rem) dp[rem] = Math.min(dp[rem], dp[rem - c] + 1);
        }
    }
    return dp[amount] > amount ? -1 : dp[amount];
}

Same recurrence, same complexity, different direction of travel. The table wins on constant factor and recursion depth; the memo wins on being written correctly in four minutes, and on visiting only reachable states.

State definition is the thing that actually fails

Almost every DP that comes out wrong in a mock interview is wrong at the state, not the loop bounds — and a state that does not carry what the recurrence needs cannot be repaired by debugging indices.

Take Longest Increasing Subsequence with the tempting broken state:

dp[i] = the length of the longest increasing subsequence among the first i + 1 elements.

The recurrence writes itself: if nums[i] > nums[i - 1] then dp[i] = dp[i - 1] + 1, else dp[i] = dp[i - 1]. On [3, 4, 1, 2] that gives dp = [1, 2, 2, 3], reporting 3. The answer is 2 (3,4 or 1,2).

The arithmetic is fine; the state is not. "Longest among the first i + 1 elements" never says what that subsequence ended on, so you cannot know whether nums[i] may legally extend it. The recurrence needs a fact the state does not carry, so it invents one, and the +1 at i = 3 chains onto a run that ended at 4. The fix carries the missing fact — dp[i] = the longest increasing subsequence ending at index i:

def length_of_lis(nums):
    dp = [1] * len(nums)                    # dp[i] = LIS ending exactly at i
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp, default=0)

Now dp[j] ends at nums[j], so nums[j] < nums[i] is decidable. The answer is max(dp), not dp[-1] — the usual tell of an "ending at" state.

Before writing a single loop, say the state out loud in one sentence, with no "sort of" in it. If you cannot, the recurrence will be wrong.

Complexity is states × work per state

Count the reachable states, count the work in one transition, multiply. That is the time. The space is the number of states you must keep, which is often fewer than the number you visit — and that gap is where space optimisation lives. Coin change: amount + 1 states, k denominations each → O(amount · k), with no squinting at loops.

The seven families

1-D sequence

One or two previous states, no second dimension. dp[i] = max(dp[i-1], dp[i-2] + nums[i]) for House Robber; Climbing Stairs is the same shape with + for max. Only two predecessors are ever read, so it collapses to O(1) space immediately.

0/1 knapsack — and the backwards inner loop

Each item taken at most once under a capacity constraint: skip it, or take it and pay out of a strictly earlier row. The 1-D form is what interviewers probe.

def knapsack(weights, values, capacity):
    dp = [0] * (capacity + 1)                  # dp[c] = best value within capacity c
    for w, v in zip(weights, values):
        for c in range(capacity, w - 1, -1):   # DESCENDING → each item used at most once
            dp[c] = max(dp[c], dp[c - w] + v)
    return dp[capacity]

The direction is not a style choice. dp[c - w] sits to the left of dp[c], so going downward guarantees it has not been written yet in this item's pass and still holds the previous row — precisely the "did not take this item" state the recurrence requires. Named problem: Partition Equal Subset Sum, knapsack with values = weights and a target of half the total; it tests whether you can see a yes/no question as a knapsack at all.

Unbounded knapsack / coin change

Identical, except an item may be reused, so the "take" branch stays on the same item. In the 1-D code that is one character:

for c in range(w, capacity + 1):   # ASCENDING → dp[c - w] may already include this item
    dp[c] = max(dp[c], dp[c - w] + v)

The bug that reuses an item in 0/1 knapsack is the feature that makes this correct. Named problem: Coin Change for the min form; Coin Change II for the counting form, worth doing separately — coins in the outer loop counts combinations, amount in the outer loop counts permutations, and both compile.

Longest increasing subsequence

The O(n²) version is above. The O(n log n) version — patience — is the follow-up:

from bisect import bisect_left

def length_of_lis(nums):
    tails = []                    # tails[k] = smallest tail of an increasing run of length k+1
    for n in nums:
        i = bisect_left(tails, n)          # bisect_right for non-DECREASING subsequences
        if i == len(tails):
            tails.append(n)
        else:
            tails[i] = n                   # a smaller tail is never worse
    return len(tails)

n states, an O(log n) search each. Be honest about what it returns: tails is not an increasing subsequence of the input, and only its length is meaningful. If they want the subsequence itself, reconstruct with a parent-index array or fall back to the quadratic version — saying that unprompted is a strong signal.

Two sequences: LCS and edit distance

A grid over two prefixes, where dp[i][j] answers for a[:i] against b[:j].

def lcs(a, b):
    dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 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[len(a)][len(b)]

Edit distance is the same grid with a different rule: on a match take the diagonal unchanged, otherwise pay 1 and take the best of delete (dp[i-1][j]), insert (dp[i][j-1]) and replace (dp[i-1][j-1]). Its base cases carry real content — dp[i][0] = i and dp[0][j] = j, because emptying a prefix costs one deletion per character. It tests whether you can name what each neighbour means rather than pattern-matching a min of three cells.

Grid paths

dp[r][c] = ways (or best cost) to reach (r, c), from the cell above and the cell to the left: dp[r-1][c] + dp[r][c-1] for counting, grid[r][c] + min(dp[r-1][c], dp[r][c-1]) for Minimum Path Sum. Named problem: Unique Paths II — an obstacle zeroes its cell, and the trap is that a blocked cell in the first row must zero everything after it in that row, which an all-ones base row gets wrong.

Interval DP

dp[i][j] = the answer for the segment i..j, filled by increasing interval length (equivalently, i descending) so the shorter segments inside already exist.

def longest_palindromic_subsequence(s):
    n = len(s)
    if n == 0:
        return 0                          # dp[0][n-1] would index backwards
    dp = [[0] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):
        dp[i][i] = 1
        for j in range(i + 1, n):
            if s[i] == s[j]:
                dp[i][j] = dp[i + 1][j - 1] + 2
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
    return dp[0][n - 1]

O(1) transition, so O(n²). Burst Balloons is the hard case: O(n²) intervals × an O(n) split → O(n³). Its lesson is that the state only works if you pick which balloon bursts last; picking the first leaves the two halves dependent on each other, and no loop fix recovers from that. State definition again, in its most expensive form.

Space optimisation, and when it is actually being asked for

Look at which states the recurrence reads. If dp[i] only reads row i - 1, you never need the other rows: 1-D sequences reduce to two scalars, 0/1 knapsack to one backwards row (O(C) space), LCS and edit distance to two rows or one row plus a saved diagonal, grid paths to one row updated in place.

The trade is reconstruction: a rolling array gives you the optimal value and discards what you need to recover the optimal choice. "What is the edit distance?" — roll it. "Show me the edits" — keep the full table. Interviewers ask "can you do better on space?" for two reasons: sometimes they want the rolling array, sometimes they are checking whether you know what it costs. Asking which reads as senior.

Greedy or DP?

One test: can you state an exchange argument in a sentence — "any optimal solution can be rewritten to make my greedy choice first without getting worse"? If you can say it and defend it, take the greedy. If you cannot, it is DP.

Coin change is the standard counterexample. With denominations {1, 3, 4} and a target of 6, greedy takes the largest coin that fits — 4 + 1 + 1, three coins. The optimum is 3 + 3, two. Taking the 4 destroys the pairing and nothing local can see that. Greedy does work on US denominations, which is exactly why an interviewer hands you an unusual set: the correctness lives in the denominations, not the algorithm.

Six problems worth drilling, and what each tests

• House Robber — a 1-D state, reduced to O(1) space without breaking it.
• Coin Change — the full route on a small problem, plus the greedy boundary.
• Partition Equal Subset Sum — seeing a yes/no question as 0/1 knapsack, and the backwards loop.
• Longest Increasing Subsequence — the "ending at i" state, and the O(n log n) follow-up.
• Edit Distance — naming what each of the three transitions means, and non-trivial base cases.
• Longest Palindromic Subsequence — interval iteration order, and reading dp[i+1][j-1] safely at length 2.

Then Climbing Stairs, Word Break, Unique Paths II, Coin Change II, Target Sum and Burst Balloons. Drill one family at a time rather than shuffling them — build the schedule with our free study-plan generator, or get live feedback on your state definitions in our DSA course.

The four failure modes

• A state that does not carry what the recurrence needs. The LIS example above; unfixable by debugging indices.
• An incomplete memo key. Caching on a subset of the arguments returns a value computed for a different subproblem.
• Off-by-one in the table dimensions. Prefix-indexed 2-D DP needs (m+1) × (n+1) cells and compares a[i-1] to b[j-1]. Mixing "index i" with "first i items" in one table is the fastest way to lose an hour.
• The inner loop running the wrong way. Descending for 0/1 knapsack, ascending for unbounded. Both run, both return a number, only one answers the question you were asked.

Write the recursion, name the state in a sentence, quote states × work per state. Do those three and you can survive DP questions you have never seen — which is the whole reason to learn families instead of solutions.

More interview patterns: Binary Search · Two Pointers · Sliding Window · Graph Algorithms

If this was useful, the rest of the pattern series arrives the same way — by email, one post at a time.

Amit Singh is a Senior SDE at Amazon, a Claude Certified Architect, and the instructor at AlgoEngineer.