Dynamic Programming Interview Questions: A Framework

Most dynamic programming interview questions are not tests of memorized solutions. They are tests of whether you can recognize a small set of recurring patterns, define a state, and write a recurrence under time pressure. If you can answer three questions fast (Is this DP? What is the state? What is the transition?), you will solve the vast majority of what Google, Meta, and Amazon throw at you. This article gives you that decision framework and maps it onto real problems from our question bank.

We run mock interviews all day, and the single biggest failure mode we see is not weak coding. It is candidates who jump straight to a recurrence without first proving to themselves the problem is even DP, then get stuck halfway with a half-correct table and no way to debug it. The fix is a repeatable process.

Step 1: Is this actually a DP problem?

Dynamic programming applies when two conditions hold. First, optimal substructure: the answer to the whole problem is built from answers to smaller subproblems. Second, overlapping subproblems: those smaller subproblems repeat, so caching their answers saves work. Dynamic programming relies on two key principles: optimal substructure and overlapping subproblems. Optimal substructure means the solution to a problem depends on optimal solutions to its subproblems.

In practice, reach for DP when you see these trigger words in the prompt:

"maximum / minimum" over a sequence of choices
"number of ways" to do something
"can you reach / is it possible" (a boolean feasibility question)
"longest / shortest" subsequence or path
a decision applied to each element (take it or skip it)

If the prompt instead rewards a single locally optimal choice at each step with no need to revisit, it is probably greedy, not DP. And if it asks for all combinations explicitly, it is backtracking. The tell for DP specifically is that a naive recursion would recompute the same state many times.

Quick example from our bank: Ways to Split Array Into Good Subarrays asks for the number of ways to split a binary array so each piece contains exactly one 1. "Number of ways" plus a decision at each boundary is a textbook DP signal, even though the final clean solution multiplies the gaps between consecutive ones.

Step 2: Name the pattern

Almost every DP interview problem is a variant of a handful of patterns. Interviewers reuse them because they cleanly separate candidates who understand the mechanics from those who pattern-matched a specific LeetCode number. Subset Sum and 0/1 Knapsack share the include/exclude invariant, but Knapsack adds a capacity dimension and an optimization objective; LCS and Edit Distance both compare two strings, but their recurrence shapes diverge because Edit Distance allows three operations while LCS only allows match or skip. Knowing where the boundaries between patterns sit is what makes them useful rather than decorative.

Here is the classification we teach, mapped to problems you can practice:

Pattern	What the state tracks	Practice problem (our bank)
Linear / "take or skip"	Best answer ending at index `i`	Maximum Sum of Subsequence With Non-adjacent Elements
Reachability on a line	Whether/how you can land on position `i`	Frog Jump
Counting splits	Ways to partition a prefix	Ways to Split Array Into Good Subarrays, Minimum Substring Partition of Equal Character Frequency
Bitmask over a small set	Which subset is already covered	Smallest Sufficient Team
Probability / expected value	Probability of being in state `i`	New 21 Game
Modular / digit DP	Remainder class mod k	Largest Multiple of Three
Combinatorial rows	Values built from the row above	Pascal's Triangle II

The 0/1 knapsack family is the one to over-learn, because so many problems reduce to it. Coin Change is an unbounded knapsack variant where you iterate forward to allow reuse, versus 0/1 knapsack which uses reverse iteration to prevent reuse. If you internalize the "for each item, include or exclude it" recurrence, Smallest Sufficient Team becomes recognizable: it is knapsack where "capacity" is a bitmask of skills still needed.

Step 3: Define the state and transition

This is where interviews are won. Say the state out loud before writing code. A good state definition answers: "What is the minimum set of variables that fully describes a subproblem?"

Work through Frog Jump. The frog's future options depend on where it is and how far it last jumped (it can jump k-1, k, or k+1 next). So the state is (stone_index, last_jump_size), and the transition tries the three jump sizes and checks whether a stone exists at the landing position. A single position is not enough state, and that is the exact trap the problem is built to catch.

Contrast that with Maximum Sum of Subsequence With Non-adjacent Elements, the classic "house robber" recurrence. Here the state is just the index, and the transition is best(i) = max(best(i-1), best(i-2) + nums[i]): skip element i, or take it and jump two back. The staff-level version layers point updates and range queries on top, which is why it pushes you toward a segment tree with a DP merge, but the core recurrence is still that one line.

For New 21 Game, the state is the probability of reaching exactly i points, and the transition sums a sliding window of previous probabilities divided by the number of draws. It looks exotic, but it is the same "sum over reachable previous states" shape as a counting DP, just with floating-point probabilities instead of integer counts.

Write the transition as a formula first. If you can write the recurrence and the base cases correctly on the whiteboard, the code is mechanical.

Step 4: Memoization or tabulation?

Both approaches cache subproblem results; they differ only in direction. Tabulation is a bottom-up approach that solves all subproblems iteratively in a specific order, storing results in a table and building the final solution from them. Memoization is top-down: write the natural recursion, then add a cache.

Our recommendation for interviews:

Start with memoization. It maps directly onto your recurrence, so you make fewer indexing errors and can explain it as you go. This matters more than raw speed on the whiteboard.
Switch to tabulation when recursion depth is a risk or when the interviewer explicitly asks to optimize. A bottom-up approach fits when you need to solve all subproblems to reach the final solution, when space efficiency is a primary concern, and when you want to avoid the risk of stack overflow from deep recursion.

For Pascal's Triangle II, tabulation is the obvious fit and the follow-up wants O(rowIndex) space: build each row in place from the previous one, iterating right to left so you do not clobber values you still need. That right-to-left trick is the same one that prevents item reuse in 0/1 knapsack, which is a nice connection to point out in an interview.

Step 5: Optimize space, then talk complexity

Once a tabulated solution works, look at how many previous rows the transition actually touches. If dp[i] depends only on dp[i-1] and dp[i-2], you can drop from an O(n) array to a couple of variables. State the time and space complexity unprompted; for most single-array DPs it is O(n) time and O(n) or O(1) space, and for 2D string or bitmask problems it is O(n*m) or O(n * 2^k).

Do not micro-optimize before you have a correct solution. We see candidates burn ten minutes hunting for O(1) space while the base recurrence is still wrong. Correct and clearly explained beats clever and broken every time.

Putting it together in a mock

A realistic loop gives you 35 to 45 minutes per coding round, and DP shows up constantly at companies known for algorithm-heavy screens. If you are targeting specific employers, our per-company breakdowns for Google, Meta, and Amazon show which patterns appear most, so you can weight your practice instead of grinding random problems.

The framework in one line: prove it is DP, name the pattern, define the state, write the recurrence, then decide top-down versus bottom-up and optimize. Practice it until steps one through three take under five minutes, because that is the part interviewers actually score.

FAQ

How many DP problems should I solve before an interview?

Aim for depth over count: 20 to 30 problems that cover each pattern in the table above, solved twice, beats 150 done once. The goal is to recognize the pattern in the first two minutes, not to have seen the exact problem. Once a new problem maps instantly to "this is knapsack" or "this is counting splits," you are ready.

Should I use recursion with memoization or a bottom-up table in the interview?

Start top-down with memoization because it follows your recurrence and is easier to reason about aloud. Move to a bottom-up table if the recursion depth could overflow the stack or the interviewer asks you to reduce space. Being able to convert between the two on request is itself a signal of understanding.

How do I tell dynamic programming apart from greedy?

Greedy works when a locally optimal choice is always globally optimal and you never need to reconsider it. DP is required when a choice depends on the results of overlapping subproblems, so you must cache and combine them. If you can construct a counterexample where the greedy pick leads to a worse total, the problem is DP.

What is the most common DP mistake candidates make?

Under-specifying the state. In problems like Frog Jump, forgetting that the last jump size is part of the state produces code that looks reasonable but fails. Always ask whether your state fully determines the subproblem before writing the transition.

Are DP questions still common in 2026 interviews?

Yes, especially at large tech companies with algorithm-focused screens. Many teams have shifted emphasis toward practical coding and system design, but DP remains a reliable filter in the coding round because it tests problem decomposition cleanly. Practicing the recognition step is a high-return use of prep time.