Dynamic Programming Interview Questions: the patterns, not the problems

Dynamic Programming Interview Questions: the patterns, not the problems

Ask engineers which interview topic they fear most and dynamic programming wins by a landslide. Strong candidates who cruise through sliding-window and tree problems freeze the moment a question smells like DP — not because they are not clever, but because they learned it as one giant topic and solved fifty problems as fifty unrelated puzzles. They retained none of them and concluded they were bad at DP. They are not. They were never given a filing system.

Here is the filing system. Underneath the costumes, almost every dynamic programming interview question belongs to one of a handful of coding interview patterns, each with a one-line tell, a short template, and a predictable trap. This guide walks through the pattern families, shows you how to name the right one within thirty seconds of reading a problem, and covers the follow-ups that actually decide the round — because at this topic, spotting the pattern and defending it out loud matters more than any single memorised recurrence.

Why dynamic programming feels impossible (and why it isn't)

Every DP problem has the same skeleton. You make a choice at each step; those choices create overlapping subproblems; greedy picking demonstrably fails, so you must remember the answers to subproblems instead of recomputing them. That is the entire mystery. The reason DP still terrifies people is that the same skeleton wears wildly different costumes: "how many ways to decode this string," "can you split this array into two equal halves," and "find the longest palindromic subsequence" do not look related, yet they are the same machine with different dials.

The first judgment call is whether a problem is DP at all or just greedy. The test is simple: try to break the greedy choice. If you can construct any input where the locally best pick leads to a globally wrong answer, you need DP. If you cannot break it, say so out loud and go greedy — interval scheduling, for instance, is greedy, not DP. Interviewers respect a candidate who tests greedy first, because it shows the decision was reasoned rather than reflexive.

The dynamic programming patterns that cover almost every question

You do not need fifty recurrences; you need the half-dozen pattern families that nearly every interview DP question reduces to, plus the judgment to recognise which one a new prompt is wearing. The table is the shortlist — the pattern, the one-line tell that gives it away, and a classic problem that lives in that family.

Pattern	The tell	Classic problem
Fibonacci-style	Answer at position i comes from a few earlier positions	Climbing Stairs, House Robber
0/1 Knapsack	Pick items once each to hit a target or budget (subset, partition)	Partition Equal Subset Sum
Unbounded Knapsack	Same, but items can be reused	Coin Change
Longest Common Subsequence	Two sequences — compare or transform one into the other	LCS, Edit Distance
Palindromic Subsequence	One string, the word palindrome, answer built from both ends	Longest Palindromic Subsequence
Longest Increasing Subsequence	Best subsequence obeying an ordering rule	LIS, Russian Doll Envelopes

A more granular view splits these into about ten (adding Linear DP, Edit Distance, Subset Sum, 2-D grid, prefix-sum and game-theory DP), but the idea is identical: each family shares an invariant — the structural property that produces the recurrence. Learn the invariant and you derive the recurrence; memorise the recurrence alone and you are stuck the moment the problem adds a twist.

Reading the pattern in 30 seconds

When a problem smells like DP — maximise, minimise, count the ways, and greedy has no proof — run the tells in order and the family falls out fast:

1. How many sequences? Two sequences means the LCS family. One string plus the word palindrome means the palindromic family.
2. Are you picking items against a budget or target? Each item once means 0/1 knapsack; reusable means unbounded knapsack.
3. Is the answer built position by position from a few previous positions? Fibonacci-style.
4. Is the answer the best chain or subsequence under an ordering rule? Longest increasing subsequence.

Each family has a template you can write almost without thinking once the state and transition are named. Fibonacci-style only looks back a fixed number of steps, so two variables beat an array — which is why interviewers love asking for the constant-space version:

# Fibonacci-style: dp[i] from a fixed number of previous positions
a, b = 1, 1
for _ in range(2, n + 1):
    a, b = b, a + b          # dp[i] = dp[i-1] + dp[i-2]  (O(1) space)

The 0/1 knapsack family decides include-or-exclude for each item under a capacity, and the inner loop runs backwards so each item is counted once:

# 0/1 knapsack reachability: inner loop BACKWARDS so each item is used once
dp = [True] + [False] * target
for x in nums:
    for s in range(target, x - 1, -1):   # right-to-left = "state before this item"
        dp[s] = dp[s] or dp[s - x]

The LCS family fills a table whose cell means "best answer using the first i characters of A and the first j of B" — match extends the diagonal, mismatch drops a character from one side:

# LCS: match extends the diagonal, mismatch drops a char from one side
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])

The follow-ups that decide a DP round

Here is where DP rounds are actually won and lost. The code is table stakes; the interviewer decides the round on the probes that come after it, and each one maps to a trap in the pattern you just used.

• "Why does the loop run backwards?" → Because iterating the sums right to left means dp[s - x] still refers to the state before this item was considered, so each item is used once. Iterate forwards and you silently allow reuse — a bug that passes small tests.
• "Is this counting or optimising?" → The same recurrence shape combines with + for "how many ways" and max for "best value". Muddling them is the most common Fibonacci-family bug; say which one you are doing out loud.
• "Combinations or permutations?" → In unbounded knapsack, putting the item loop outside the amount loop counts combinations; inside, it counts ordered sequences. Interviewers use this exact distinction to test whether you understand your own table.
• "Can you drop a dimension to O(1) space?" → Flattening a memoised table to a rolling row (the two-variable Fibonacci, the 1-D knapsack) is the senior move. Offer it; write it if asked.
• "Memoise or tabulate?" → Discover the recurrence top-down (brute recursion plus a cache — it matches how humans think), then convert bottom-up for space if needed. "I'll memoise first, then flatten it" is a perfectly senior answer.

On a live round the interviewer rarely stops when your DP passes. "Good. Now why is the inner loop going backwards — and what breaks if I make it forwards?" A memorised template cannot answer that. The candidate who can say why, in one sentence, is the one who passes.

Each of those probes is read on the four dimensions a scored round grades: problem solving (did you name the right pattern and derive the recurrence), communication (did you narrate the state and transition before coding), technical execution (clean, correct code with the boundary rows right), and time management (did you reach a working solution and still have time for the follow-up). Reading this list teaches you the answers; it does not teach you to deliver them while someone changes the dial.

Coding
Company-agnostic · Onsite coding · 45 min
Solve a DP problem out loud and defend the recurrence under follow-ups

Practise on Zynter →

How to practise dynamic programming

The mistake almost everyone makes is grinding a hundred DP problems in random order, retaining them for a week, and fearing the topic forever. The problems never get filed under a reusable shape. Do this instead — it is the best way to practise coding interviews for DP specifically:

• Learn the patterns in order, each building on the last, and do four to six problems per pattern in rising difficulty. That is roughly thirty problems for command of the whole topic, not a hundred.
• Write the tell in your own words after every problem. If you cannot state the trigger in one sentence, you have not filed it.
• Interleave families. Ten LCS problems in a row build LCS familiarity but not the ability to tell LCS from Edit Distance when both involve two strings — and that selection is what the interview measures.
• Say the diagnosis out loud. "Two strings, compare and transform, so this is the LCS family; the state is prefixes of both." That one sentence shows method, not luck.
• Finish with timed mocks. In the last stretch, solve under a 45-minute clock while narrating, because the clock and the follow-up are the part reading alone can never rehearse.

If you want raw volume to drill the mechanics first, PipeCode is a sister platform built for structured problem reps; use it to build the muscle, then come back here to rehearse spotting and defending the pattern out loud.

Coding
Company-agnostic · Phone screen · 45 min
Rehearse naming the DP pattern in the first 30 seconds, out loud

Practise on Zynter →

Frequently asked questions

What are the main dynamic programming patterns?

Most interview DP reduces to a small set of families: Fibonacci-style (the answer at a position comes from a few earlier ones), 0/1 knapsack (pick each item once to hit a target), unbounded knapsack (items reusable), longest common subsequence (two sequences you compare or transform), palindromic subsequence (one string, worked inward from both ends), and longest increasing subsequence (the best chain under an ordering rule). A finer split adds linear DP, edit distance, subset sum, 2-D grid, prefix-sum and game-theory DP, but those six families carry most of the weight. Learn each one's invariant and you can derive the recurrence rather than recall it.

How do I know if a problem is dynamic programming and not greedy?

Try to break the greedy choice. If you can construct an input where the locally best pick leads to a globally wrong answer, the problem needs DP; if you cannot, it is probably greedy and you should say so and go greedy. DP problems also tend to ask you to maximise, minimise, or count the ways, with choices that create overlapping subproblems. Testing greedy first and explaining why it fails is itself a strong signal — it shows the decision was reasoned, not reflexive.

Should I use memoisation or tabulation in an interview?

Use whichever gets you to a correct solution fastest, which for most people is top-down memoisation — write the brute-force recursion and add a cache, because that matches how you actually reason about the choices. Then mention that you can convert to bottom-up for tight space control, and do it if the interviewer asks or the constraints demand it. Being able to flatten a memoised solution to constant space, like the two-variable Fibonacci, is the part that reads as senior. Arguing about which is "correct" just wastes time you need.

How many DP problems should I solve to be ready?

About thirty, if they are organised by pattern — four to six per family in rising difficulty — rather than a hundred solved at random. The goal is not a completion count; it is whether you can read an unfamiliar problem, name the pattern in the first thirty seconds, and reach a working recurrence within a few minutes. A better readiness signal than "I solved 100 problems" is being able to diagnose a problem you have never seen and explain your state and transition out loud.

Why can I understand DP solutions but not write them myself?

Because understanding a solution is recognition, which is passive, while constructing one requires you to identify the invariant, define the state, and derive the transition from scratch. If you practise mainly by reading solutions, you train recognition and not construction, so the blank page still defeats you. Close the gap by practising the derivation itself — cover the solution, name the pattern, and rebuild the recurrence — and by re-solving a problem you missed a few days later without looking.

How do I practise DP interview questions out loud?

Reading a recurrence is not the same as defending it while someone asks "why backwards?" On Zynter, the Coding track runs live voice rounds modelled on how real company loops run — a 45-minute round, a real editor where your code compiles and runs, and a voice interviewer that asks the DP follow-ups one at a time, then gives you a debrief on problem solving, communication, technical execution and time management. You get genuine mock-coding-interview feedback on demand, and the score is a practice signal, not a hiring decision.

Practise it on Zynter

You can memorise every recurrence. The DP round is won on "why backwards?" — said out loud, under the clock.

Pick a coding round, write a DP solution that runs in a real editor, and defend it to a voice interviewer that keeps asking "is this counting or optimising?" and "can you drop a dimension to O(1) space?" — then read the debrief. Zynter.ai is on-demand mock interviews modelled on real company loops, with 150+ rounds across 20 companies (Sep 2026) — about $8–$12 for a full 60-minute mock, and two free credits to start.

Practise a coding round →
Browse all interview tracks