Dynamic Programming Patterns for Coding Interviews (2026)

Dynamic programming solves problems with overlapping subproblems and optimal substructure by computing each subproblem once and reusing the answer. It's the pattern Google over-indexes on and the one most candidates fear — usually because they jump to code instead of writing the recurrence first.

The reliable path: define the state, write the recurrence (top-down with memoization), then optionally convert to a bottom-up table. Here's how to recognize DP and three worked examples.

When to recognize this pattern

The problem asks for the number of ways, the min/max of something, or whether something is possible — over a sequence of choices.
A greedy approach gives wrong answers on some input (you must consider combinations of choices).
The naive recursion recomputes the same subproblems — the signal to memoize.

The template

Start top-down: write the recursion, then add a cache. This is easier to derive than jumping straight to a table.

from functools import lru_cache

def solve(n):
    @lru_cache(maxsize=None)
    def dp(state):
        if base_case(state):
            return base_value
        return best(dp(next_state) for choice in choices(state))
    return dp(initial_state)

# Then optionally convert to bottom-up:
# dp = [base] * (n + 1)
# for i in range(1, n + 1):
#     dp[i] = best(dp[i - c] for c in choices)

Worked examples

Climbing stairs (1-D DP)

Problem: You can climb 1 or 2 steps at a time. How many distinct ways to reach step n?

Each step is reachable from the one or two below it, so dp[i] = dp[i-1] + dp[i-2] — Fibonacci.

def climbStairs(n):
    prev, curr = 1, 1
    for _ in range(n - 1):
        prev, curr = curr, prev + curr
    return curr

O(n) time, O(1) space by keeping only the last two states. Recognizing this as Fibonacci is the whole insight.

Coin change (unbounded DP)

Problem: Given coin denominations and an amount, return the fewest coins to make the amount, or -1.

dp[a] is the min coins for amount a; try every coin and take the best.

def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    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

O(amount × coins) time. The unbounded part: each coin can be reused, so we look back to dp[a-c] in the same array, not a previous row.

Longest common subsequence (2-D DP)

Problem: Given two strings, return the length of their longest common subsequence.

A 2-D table where dp[i][j] is the LCS of the first i and j characters. Match → diagonal + 1; else take the better of dropping one character.

def longestCommonSubsequence(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]

O(m×n) time and space. The 2-D table is the template for most string-pair DP (edit distance, etc.); the recurrence changes but the grid stays.

Variations & pitfalls

1-D vs 2-D. One sequence of choices → 1-D array; two interacting sequences (or a grid) → 2-D table.
Top-down vs bottom-up. Memoized recursion is easier to derive; tabulation is often faster and avoids recursion limits. Derive top-down, convert if needed.
Pitfall: coding before writing the recurrence. State the subproblem and transition in one sentence first — the code follows.

Find the recurrence faster with live AI support

CoPilot Interview surfaces the optimal pattern and a working solution with Big-O in about 4 seconds during real Zoom and Teams calls. Free for Windows and macOS, invisible on screen-share.

Download free

FAQ

How do I know a problem is dynamic programming?

Look for: asking the number of ways, the min/max, or whether something is possible over a sequence of choices; a greedy approach that fails on some inputs; and naive recursion that recomputes the same subproblems. Those three signals together almost always mean DP.

Should I write DP top-down or bottom-up?

Derive it top-down first - write the plain recursion, then add memoization (a cache). It's much easier to reason about. Convert to bottom-up tabulation afterward if you need the speed or want to avoid recursion-depth limits.

What's the difference between 1-D and 2-D DP?

Use a 1-D array when there's a single sequence of choices (climbing stairs, house robber, coin change). Use a 2-D table when two sequences interact (longest common subsequence, edit distance) or you're moving through a grid (unique paths).

Why does Google ask so much dynamic programming?

Google's interviews over-index on DP and graphs relative to other companies. DP cleanly tests whether you can spot overlapping subproblems and derive a recurrence - exactly the structured reasoning they grade. Weight DP heavily for a Google loop.

What's the biggest dynamic programming mistake in interviews?

Coding before writing the recurrence. Define the state (what dp[i] means) and the transition (how it's built from smaller states) in one sentence each first; the implementation then falls out and you avoid getting lost.

Dynamic Programming Patterns