Dynamic programming interview patterns: spot the problem, build the table, say it out loud

A dynamic programming interview problem asks for a best value, a count of ways, or a yes or no answer that you can build from answers to smaller versions of the same problem. You solve it by naming the state, writing the transition between states, and fixing the base cases. Most interview DP falls into five families: 1D sequences, grid paths, knapsack, two-string comparison and intervals.

What is dynamic programming in a coding interview?

Dynamic programming is recursion that remembers. A problem suits it when two things are true. First, the best answer for the whole input is built from best answers for smaller inputs. Second, the same smaller inputs come up again and again, so a plain recursive solution repeats work.

Counting the ways to climb n stairs one or two steps at a time is the standard example. Naive recursion branches twice per call and grows exponentially, yet there are only n distinct subproblems. Store each answer once and the work drops to linear.

How do you spot a DP problem?

The prompt rarely says "dynamic programming". It usually carries one or more of these signals.

• The ask is a number, not a list: the minimum cost, the maximum profit, the number of ways, the length of the longest something.
• Each step is a choice (take or skip, go right or go down, match or don't) and today's choice limits tomorrow's options.
• A brute force exists but tries every combination, and you can see the same partial state being reached by different paths.
• The answer for a prefix, a suffix, a sub-grid or a sub-range would help you answer the full input.
• The input size fits a table. As a rough rule, a few thousand elements suggests an O(n²) table is acceptable, and a few hundred suggests O(n³) may be.

Two signals point away from DP. If the prompt wants every solution listed, such as all permutations, that is backtracking. If one local choice is always safe, a greedy solution is simpler. When unsure, look for a small counterexample to the greedy rule. If you find one, use DP.

The recipe: state, transition, base case

Every DP solution answers the same five questions. Say them out loud in this order and the code mostly writes itself.

1. Define the state in words. Write one sentence of the form "dp[i] is the best answer for the first i items" or "dp[i][j] is the answer for a[:i] and b[:j]". If you cannot say it in one sentence, the state is wrong or missing a dimension.
2. Write the transition. Express dp[i] using smaller states. The transition usually mirrors the choice in the prompt: take this item or skip it, come from above or from the left.
3. Fix the base cases. The smallest inputs you can answer without a transition: zero items, an empty string, the first row of a grid. Most off-by-one bugs live here.
4. Choose the order. Fill states so that everything a transition reads is already computed. For prefixes that means left to right. For intervals it means short ranges before long ones.
5. Locate the answer. Say where the final answer sits: dp[n], dp[m][n], or the maximum over the whole table.

Top-down versus bottom-up

Top-down DP is a recursive function plus a cache. You write the recurrence directly and let memoization skip repeated calls. In Python, functools.lru_cache does the caching for you.

from functools import lru_cache

def climb_stairs(n):
    @lru_cache(maxsize=None)
    def ways(i):
        if i <= 1:          # base case: one way to stand on step 0 or 1
            return 1
        return ways(i - 1) + ways(i - 2)
    return ways(n)

print(climb_stairs(5))   # 8

The function reads like the recurrence: the ways to reach step i are the ways to reach i minus 1 plus the ways to reach i minus 2. The cache means each value of i is computed once, so the run time is O(n).

Bottom-up DP fills a table in a loop, starting from the base cases. It avoids recursion entirely, which matters in Python because the default recursion limit is 1,000 frames, and a top-down solution on a large input can hit it. Bottom-up also makes space optimization possible, because you can see exactly which earlier cells each step reads.

In an interview, start with whichever form is clearer, then offer to convert. That shows you understand both.

The core dynamic programming patterns

Interview DP problems reuse a small number of shapes. Learn the recurrence for each family in words, and new problems start to look like old ones with different names.

1D sequences: climbing stairs and house robber

The state is a position in a sequence. Climbing stairs: the ways to reach step i equal the ways to reach step i minus 1 plus the ways to reach step i minus 2. House robber, where you cannot take two adjacent houses: the best total up to house i is the larger of the best up to house i minus 1 (skip this house) and the best up to house i minus 2 plus this house's value (take it).

def rob(nums):
    # best[i] = max(best[i-1], best[i-2] + nums[i]), kept in two variables
    prev2, prev1 = 0, 0
    for x in nums:
        prev2, prev1 = prev1, max(prev1, prev2 + x)
    return prev1

print(rob([2, 7, 9, 3, 1]))  # 12 (2 + 9 + 1)
print(rob([]))               # 0

Because each step reads only the two previous values, two variables replace the whole array. Time is O(n) and extra space is O(1). The empty list returns 0 without a special case, which is worth pointing out when you test.

2D grid paths

The state is a cell. If you can move only right or down, the number of paths to a cell equals the paths to the cell above plus the paths to the cell on the left. The first row and first column each have one path. Minimum path sum uses the same shape with a different combine step: the cheapest cost to a cell is its own cost plus the smaller of the cost from above and the cost from the left. Blocked cells simply hold zero paths.

Knapsack

The state is an item index and a remaining capacity. In 0/1 knapsack, each item is used at most once: the best value using the first i items with capacity c is the larger of skipping item i, or taking it and adding its value to the best for the first i minus 1 items with capacity c minus its weight. Subset sum is the same problem with true or false in place of values.

The unbounded version, where an item can be reused, covers coin change. The fewest coins for amount a is one plus the fewest coins for a minus some coin, minimized over all coins. Counting the ways to make change is similar, but the loop order matters: put coins in the outer loop so each combination is counted once rather than once per ordering.

Two strings: longest common subsequence

The state is a pair of prefix lengths. If the last characters of a[:i] and b[:j] match, the LCS is one more than the LCS of both prefixes shortened by one. If they differ, it is the larger of dropping the last character of a or dropping the last character of b. Edit distance, shortest common supersequence and many string-matching problems use the same table with different rules.

def lcs(a, b):
    m, n = len(a), len(b)
    # dp[i][j] = LCS length of a[:i] and b[:j]; row 0 and column 0 stay 0
    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]

print(lcs("abcde", "ace"))  # 3
print(lcs("abc", "def"))    # 0

The extra row and column of zeros are the base cases: an empty prefix shares nothing with anything. Time and space are both O(m × n). The answer is in the bottom-right cell.

Intervals

The state is a range i to j. The best answer for the range comes from trying every split point k inside it and combining the best for the left part, the best for the right part, and the cost of the split itself. Matrix chain multiplication, bursting balloons and minimum palindrome partitioning follow this shape. Fill the table by increasing range length so both halves are ready. There are about n² ranges and up to n split points for each, so expect O(n³) time.

Space optimization

Once the bottom-up version works, look at which cells each transition reads. If row i only reads row i minus 1, keep two rows, or often one. LCS drops from O(m × n) to O(n) memory this way. The 1D sequence problems drop to a few variables, as in the house robber sample.

Two details trip people up. In 0/1 knapsack with a single array, loop capacity from high to low, so each item is counted once. Looping low to high quietly turns it into the unbounded version. And compressing the table means you lose the ability to reconstruct which choices built the answer. If the interviewer asks for the actual subsequence or item list, keep the full table or store the choices.

Worked example: narrating house robber

Here is an invented example of how a candidate might talk through house robber in a live round. Notice that the state sentence comes before any code.

"I can't take two neighbours, so each house is a take or skip choice that affects the next one. That makes me think of DP. Let best of i be the most I can collect from the first i houses. For house i, I either skip it and keep best of i minus 1, or take it and add its value to best of i minus 2. Base case: zero houses gives zero. I only ever look back two steps, so I'll keep two variables instead of an array. That's O(n) time and O(1) space. Let me test it on 2, 7, 9, 3, 1. I expect 12, from 2 plus 9 plus 1, and I'll check the empty list too."

It covers the signal, state, transition, base case, complexity and two tests. A common follow-up is houses in a circle: run the same function twice, once without the first house and once without the last, and take the larger result.

How to narrate a DP solution out loud

DP reasoning is easy to keep in your head and never say. A few habits help.

• Name the signal before the technique. "I keep reaching the same partial state from different paths" is better than announcing "this is DP".
• Say the state as a full sentence and write it down. Every later question refers back to it.
• Draw a tiny table for a small input. Filling three or four cells aloud catches transition bugs before you type them.
• State time and space as "number of states times work per state". It is an honest way to derive complexity rather than recall it.

Common mistakes

1. Coding before defining the state. Without a one-sentence definition, transitions drift and the base cases don't line up with them.
2. Off-by-one between dp indices and input indices. If dp[i] covers the first i items, the current item is nums[i - 1]. Decide once and say it.
3. Wrong fill order. A transition that reads a cell you haven't computed yet returns a default zero and a wrong answer that looks plausible.
4. Forcing greedy. A greedy rule that works on the example can fail on another input. Test it against one counterexample before committing.
5. Forgetting recursion depth. A top-down Python solution on a large input can exceed the recursion limit. Mention it and offer the loop version.

A practice loop for DP problems

One problem per pattern, solved aloud, teaches more than ten solved silently.

1. Pick one family. Work on 1D sequences for a few days, then grids, then knapsack, strings and intervals. Mixing families too early makes every problem feel new.
2. Set a timer for 25 minutes. Say the signal, the state, the transition and the base case before you type. Then code and test.
3. Write the recurrence in words afterwards. One sentence per problem in a notebook. Over time this becomes your pattern sheet.
4. Redo it two days later. From a blank editor, without looking. If the state sentence comes back quickly, the pattern has stuck.

The timing and narration habits are the same as any coding round. Live coding mock interview: narrate under a timer covers how to run one honestly.

Practice DP on the Live coding surface

HIDEA AI has four separate surfaces: Verbal, Live coding, System design and Project. For DP practice, use Live coding. You capture the problem from the screen, and the response leads with a plain-English approach, then code in the language you picked, then time and space complexity. Python is one of the 18 supported languages.

Use it after you have tried the problem yourself. Say your state and transition aloud first, write your own solution, then compare your recurrence and complexity with the response. You still speak or type every answer. Fifteen session minutes a day is free, with no credit card, on the macOS and Windows desktop app. The interview copilot overview lists every surface, and the pricing page shows the plans.

Where to go next

• See where DP fits among the other shapes: coding interview patterns.
• Graph problems are the other big family: graph algorithms interview questions.
• Plan your weeks: a two-week technical interview preparation plan.
• Ready to practice? Download the app for macOS or Windows.