SpaceComplexity

Dynamic Programming Patterns Cheat Sheet for Interviews

June 6, 202612 min read
dsaalgorithmsinterview-prepdynamic-programming
Dynamic Programming Patterns Cheat Sheet for Interviews
TL;DR
  • Linear 1D DP compresses to O(1) space with two variables; the most common trap is initializing dp[0] to 0 instead of nums[0].
  • 0/1 knapsack scans the weight dimension right-to-left to prevent reusing an item within a single pass.
  • Unbounded knapsack scans left-to-right because reusing the current item within a pass is exactly the goal.
  • Interval DP fills by interval length, not starting index; filling row-by-row produces wrong answers in O(n³).
  • Bitmask DP encodes every subset as an integer and is only applicable when n is 20 or fewer.
  • State machine DP requires drawing the transition diagram before coding — stock cooldown bugs always come from skipping this step.
  • Tree DP returns a tuple per DFS node in post-order; the return value and the global answer are different values.

Dynamic programming has a reputation problem. Half the engineers who study it feel like they're learning dark magic. The other half think they understand it until they see a problem in an interview and their brain quietly submits a 503.

What nobody tells you upfront: you don't need to understand the full theory. Ten patterns cover 90% of what shows up in coding interviews. Each one below maps to its recognition signal, state definition, recurrence, complexity, and a tight code template. If you already know DP is just recursion with a memory, this will sharpen what you already have.

How to Know You're Looking at a DP Problem

Two properties must both hold. First, overlapping subproblems: naive recursion recomputes the same inputs repeatedly. Second, optimal substructure: the optimal answer to the whole problem is built from optimal answers to smaller subproblems.

If the problem says "number of ways", "minimum cost", "maximum value", "can you reach", or "longest", treat it as a DP candidate. "Distinct" or "non-adjacent" as modifiers usually shape the recurrence. Seeing "minimum" with no obvious greedy structure is basically the problem whispering "try DP" directly into your ear. For a deeper look at reading these signals, see how to recognize dynamic programming problems.

Pattern 1: Linear 1D (Fibonacci Family)

Signal: Answer at position i depends only on a fixed lookback window (1-3 previous states). House Robber, Climbing Stairs, Jump Game.

State: dp[i] = best answer considering the first i elements.

Recurrence (House Robber): dp[i] = max(dp[i-1], dp[i-2] + nums[i])

Complexity: O(n) time, compresses to O(1) space with two variables.

Trap: Initializing dp[0] incorrectly. For House Robber, dp[0] = nums[0] not 0. It's an easy mistake, especially when you're nervous and moving fast. The wrong initialization doesn't crash. It just silently produces wrong answers on edge cases.

def rob(nums):
    prev2, prev1 = 0, 0
    for n in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + n)
    return prev1

Pattern 2: 0/1 Knapsack

Signal: Each item can be used at most once. "Partition into equal subsets", "target sum", "can you pick items to reach W".

State: dp[w] = True/max value achievable with capacity w.

Recurrence: dp[w] = max(dp[w], dp[w - weight[i]] + value[i])

Complexity: O(n * W) time, O(W) space.

Scan the weight dimension in reverse. Forward scanning lets an item be used multiple times within a single pass because you read the updated value. Backward scanning ensures you only read values from before the current item was considered. This is the most commonly forgotten rule in the entire cheat sheet. Write it on your hand if you have to.

def knapsack(weights, values, W):
    dp = [0] * (W + 1)
    for w, v in zip(weights, values):
        for cap in range(W, w - 1, -1):   # backward
            dp[cap] = max(dp[cap], dp[cap - w] + v)
    return dp[W]

Pattern 3: Unbounded Knapsack

Signal: Each item can be used any number of times. Coin Change, Coin Change II, Rod Cutting.

State: Same shape as 0/1 knapsack, dp[w].

Recurrence: dp[w] = min(dp[w], dp[w - coin] + 1)

Complexity: O(n * W) time, O(W) space.

Scan forward. When you compute dp[w], dp[w - coin] already reflects the current item being available again. That reuse is what makes items unbounded. It's the same shape as 0/1 knapsack but you flip the scan direction, which is either elegant or maddening depending on how your interview is going. See memoization vs tabulation to see how this maps to the top-down version.

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

Pattern 4: Two-Sequence DP (LCS / Edit Distance)

Signal: Two strings or arrays, comparing or aligning them. LCS, Edit Distance, Shortest Common Supersequence.

State: dp[i][j] = answer for the first i chars of s1 and first j chars of s2.

Recurrence (Edit Distance):

  • If s1[i-1] == s2[j-1]: dp[i][j] = dp[i-1][j-1]
  • Else: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])

Complexity: O(m * n) time, compresses to O(min(m, n)) space with a rolling row.

Trap: Off-by-one in base cases. dp[i][0] = i and dp[0][j] = j for Edit Distance. The indexing is a 1-based string, 0-based DP table situation, and it's responsible for an embarrassing percentage of wrong answers on this family of problems.

def minDistance(s1, s2):
    m, n = len(s1), len(s2)
    dp = list(range(n + 1))
    for i in range(1, m + 1):
        prev = dp[0]; dp[0] = i
        for j in range(1, n + 1):
            temp = dp[j]
            if s1[i-1] == s2[j-1]: dp[j] = prev
            else: dp[j] = 1 + min(prev, dp[j], dp[j-1])
            prev = temp
    return dp[n]

The classic "only two hard problems in CS" list, which itself has off-by-one errors in its numbering Off-by-one errors: the DP base case is always wrong in exactly the way you didn't think to check.

Pattern 5: Longest Increasing Subsequence (LIS)

Signal: "Longest subsequence where each element is strictly greater than the previous."

State (O(n²)): dp[i] = length of LIS ending at index i.

Recurrence: dp[i] = max(dp[j] + 1 for j < i if nums[j] < nums[i])

O(n log n) approach (patience sorting): Maintain a tails array where tails[k] is the smallest tail of any increasing subsequence of length k+1. Binary search to find the insertion point.

Complexity: O(n²) time / O(n) space for the simple DP. O(n log n) time / O(n) space for the tails approach.

The tails array does not store the actual LIS. It only gives you the correct length. If you need to reconstruct the sequence, you need a separate parent-tracking array. Interviewers love asking for reconstruction immediately after you implement the tails approach. Stay ready.

import bisect
def lengthOfLIS(nums):
    tails = []
    for n in nums:
        pos = bisect.bisect_left(tails, n)
        if pos == len(tails): tails.append(n)
        else: tails[pos] = n
    return len(tails)

Pattern 6: Grid / Path DP

Signal: 2D grid, count paths or minimize cost moving right/down. Unique Paths, Min Path Sum, Dungeon Game.

State: dp[i][j] = answer to reach cell (i, j).

Recurrence (Min Path Sum): dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

Complexity: O(m * n) time, compresses to O(n) with a single row array.

Dungeon Game requires reverse direction. The minimum health at a cell depends on what comes after it, not before. Fill from bottom-right to top-left. Forward fill is wrong for any problem with future constraints. If your state requires knowing the future, you fill the table from the future backward.

def minPathSum(grid):
    m, n = len(grid), len(grid[0])
    dp = [float('inf')] * (n + 1)
    dp[n - 1] = 0
    for i in range(m - 1, -1, -1):
        new_dp = [float('inf')] * (n + 1)
        for j in range(n - 1, -1, -1):
            new_dp[j] = grid[i][j] + min(dp[j], new_dp[j + 1])
        dp = new_dp
    return dp[0]

Pattern 7: Interval DP

Signal: You pick an element inside a range and the cost depends on what's left. Burst Balloons, Matrix Chain Multiplication, Strange Printer.

State: dp[i][j] = optimal cost for the subproblem on range [i, j].

Recurrence (Burst Balloons): dp[i][j] = max(dp[i][k-1] + dp[k+1][j] + nums[i-1]*nums[k]*nums[j+1]) over all k in [i,j].

Complexity: O(n³) time, O(n²) space.

Fill by length, not by starting index. All subproblems of length 2 must be solved before length 3. Filling row by row (outer loop on i) violates this dependency and produces wrong answers. This pattern shows up almost exclusively in Google-style and quant finance interviews, which is either reassuring or terrifying depending on where you're interviewing.

def maxCoins(nums):
    nums = [1] + nums + [1]
    n = len(nums)
    dp = [[0] * n for _ in range(n)]
    for length in range(2, n):          # fill by length
        for i in range(0, n - length):
            j = i + length
            for k in range(i + 1, j):
                dp[i][j] = max(dp[i][j],
                    dp[i][k] + dp[k][j] + nums[i]*nums[k]*nums[j])
    return dp[0][n-1]

Pattern 8: Tree DP

Signal: Answer involves choices at each node that depend on subtree results. Binary Tree Maximum Path Sum, House Robber III, Diameter of Binary Tree.

State: A tuple returned from each DFS call, one value per mode the node can be in (included vs excluded).

Recurrence: Post-order: compute children first, then the parent's state from children's results.

Complexity: O(n) time, O(h) space for the call stack.

The return value from the DFS is not always the final answer. For path problems, the global answer updates inside the DFS while the return value is the best you can pass upward (which has different constraints than a standalone path). This trips people up more than any other aspect of tree DP. The function returns one thing; the answer lives somewhere else.

def rob(root):
    def dfs(node):
        if not node: return (0, 0)   # (with_node, without_node)
        lw, lwo = dfs(node.left)
        rw, rwo = dfs(node.right)
        with_node = node.val + lwo + rwo
        without_node = max(lw, lwo) + max(rw, rwo)
        return (with_node, without_node)
    return max(dfs(root))

Pattern 9: State Machine DP

Signal: A transaction or mode (buy/sell/hold/cooldown) with defined transitions between states. Best Time to Buy and Sell Stock series.

State: dp[state] per day, where states are nodes in a finite machine.

Complexity: O(n * states) time, O(states) space.

Draw the state machine before writing any code. Once states and transitions are clear, the recurrence writes itself. Skipping this step on stock problems causes off-by-one errors on cooldown constraints, which are especially embarrassing because the interviewer can see that you're just guessing at +1 and -1 adjustments until something passes.

def maxProfit(prices):
    # States: held, sold (cooldown), rest
    held = -float('inf')
    sold = 0
    rest = 0
    for p in prices:
        held, sold, rest = (
            max(held, rest - p),
            held + p,
            max(rest, sold)
        )
    return max(sold, rest)

Pattern 10: Bitmask DP

Signal: n <= 20 with "visit all", "assign each to one group", or "cover all elements". TSP, Minimum Cost to Connect All Points (Held-Karp), Stickers to Spell Word.

State: dp[mask][i] = optimal cost having visited exactly the nodes in mask, currently at node i.

Recurrence (TSP): dp[mask | (1<<j)][j] = min(dp[mask][j], dp[mask][i] + dist[i][j])

Complexity: O(2^n * n²) time, O(2^n * n) space.

The exponential state space is the point. This is not a flaw to optimize away; the 2^n states encode every possible subset. If n > 20, bitmask DP is the wrong tool. And if you see this problem in an interview, congratulations: you're at a company that genuinely wants to know if you've seen Held-Karp.

def shortestPath(graph, n):
    dp = [[float('inf')] * n for _ in range(1 << n)]
    dp[1][0] = 0
    for mask in range(1 << n):
        for u in range(n):
            if not (mask >> u & 1): continue
            for v in range(n):
                if mask >> v & 1: continue
                dp[mask | (1 << v)][v] = min(
                    dp[mask | (1 << v)][v],
                    dp[mask][u] + graph[u][v])
    full = (1 << n) - 1
    return min(dp[full])

Quick Reference Table

PatternState ShapeScan OrderSpace Optimization
Linear 1Ddp[i]Left to rightO(1) with two vars
0/1 Knapsackdp[w]Weights: right to leftO(W)
Unbounded Knapsackdp[w]Weights: left to rightO(W)
Two-Sequencedp[i][j]Row by rowO(min(m,n)) rolling row
LISdp[i] or tailsLeft to rightO(n)
Grid / Pathdp[i][j]Top-left to bottom-right (or reverse)O(n) rolling row
Intervaldp[i][j]By interval lengthO(n²), no shortcut
TreeTuple per nodePost-order DFSO(h) stack
State Machinedp[state]Left to rightO(states)
Bitmaskdp[mask][i]By mask popcountO(2^n * n), no shortcut

Which Dynamic Programming Patterns Get Tested Most

Patterns 1 through 6 cover the vast majority of what you'll face. Linear 1D and Grid problems show up everywhere. Two-sequence DP (LCS / Edit Distance) is a staple at every tier. 0/1 and Unbounded Knapsack are common disguised as partition and coin problems.

Patterns 7 (Interval) and 10 (Bitmask) are almost exclusive to Google-style and quantitative finance interviews. Pattern 9 (State Machine) often appears as a multi-part series in Meta interviews, where each part adds a new state. Pattern 8 (Tree DP) shows up mid-level and above across the board.

If you're within a week of your interview and haven't practiced saying your recurrences out loud, you're not ready. Knowing a pattern on paper and retrieving it under 45 minutes of pressure while narrating your thought process are two completely different skills. That's exactly the gap SpaceComplexity addresses: pattern recognition under real interview conditions, with voice, not just code. For the greedy vs DP boundary, see greedy vs dynamic programming.

Further Reading