Top Dynamic Programming Interview Questions to Practice

Dynamic programming interview questions test whether you can turn a large problem into smaller states and reuse their answers. These five classics build from a simple one-dimensional recurrence to a two-string table, with each problem testing a different decision pattern.

We analyzed the published like and dislike counts on the 5 LeetCode pages for these dynamic programming problems and found Climbing Stairs leads with 25,036 likes and 26,103 total votes. House Robber, Longest Increasing Subsequence, Coin Change, and Longest Common Subsequence each drew fewer likes, from 24,005 down to 15,384.

Table of Contents

• Climbing Stairs: A first practice problem for recurrence thinking
• House Robber: Practice making choices across a sequence
• Coin Change: Build confidence with unbounded choices
• Longest Increasing Subsequence: Learn to track sequence progress
• Longest Common Subsequence: Handle two-dimensional DP states
• Compare the five questions by pattern, state, and complexity
• Frequently asked questions
• Conclusion

1. Climbing Stairs: A first practice problem for recurrence thinking

Climbing Stairs asks how many ways you can reach the top if each move climbs one or two steps. It’s a good first problem because the last move can only come from one step below or two steps below.

Define dp[i] as the number of ways to reach step i. Then dp[i] = dp[i - 1] + dp[i - 2]. The base cases are dp[0] = 1 and dp[1] = 1, so the first step has one way to reach it. The empty set of moves counts as one way to reach step zero, which makes the recurrence work cleanly.

For example, reaching step four means the final move came from step three or step two. Add the ways to reach those two steps. The recurrence is simple, but it gives you a useful habit: describe the state before writing code. That is the core of dynamic programming: solve smaller subproblems once and store their results in a table.

The direct recursive version repeats work. A cached top-down solution stores each result, while a bottom-up version fills the values in order. Since each value needs only the prior two, you can keep two rolling variables instead of an entire array.

• Pattern: One-dimensional counting.
• Time: O(n).
• Space: O(1) with rolling values.

In an interview, say why each value depends on the two earlier states. That explanation matters more than memorizing the Fibonacci-like formula.

2. House Robber: Practice making choices across a sequence

House Robber asks for the largest sum from a row of houses when you can’t choose two neighbors. It’s useful practice for problems where each position creates a take-or-skip choice.

Let dp[i] be the best total using houses through index i. If you skip house i, keep dp[i - 1]. If you rob it, add its value to dp[i - 2], since the previous house is off limits. So the recurrence is dp[i] = max(dp[i - 1], dp[i - 2] + house[i]).

Try values [2, 7, 9, 3, 1]. At the third house, taking its value of nine combines with the best total from two houses earlier. The choice isn’t simply “take the larger house.” A smaller house can be part of the best total if it leaves room for another non-adjacent pick.

The first two values need careful handling. With one house, the answer is that house’s value; with two, it’s the larger value. For an empty input, return zero. Once those cases are clear, the linear solution takes O(n) time. It can use O(1) space by keeping only the best totals for the last two positions.

A circular version adds one wrinkle: the first and last houses are neighbors. Solve one case without the first house and another without the last, then take the better result.

3. Coin Change: Build confidence with unbounded choices

Coin Change asks for the fewest coins needed to make a target amount, with each denomination available as many times as needed. It tests whether you can model an unbounded choice and avoid a tempting but unreliable greedy rule.

Define dp[a] as the fewest coins needed to make amount a. Start with dp[0] = 0. For each amount, try every coin that fits and use dp[a] = min(dp[a], dp[a - coin] + 1). If no coin combination reaches the target, return -1.

Say the coins are [1, 3, 4] and the target is six. Taking the largest coin first uses four, then two ones, for three coins total. Two coins of value three are better. The DP considers each valid last coin, so it doesn’t lock into a locally attractive choice.

The table has one state for each amount, and each state checks the available denominations. With target amount A and C coin types, that takes O(A × C) time and O(A) space. Use a sentinel value for amounts you can’t yet make, and check that a prior amount is reachable before adding one.

The counting version is a different question. If the prompt asks how many combinations make the amount, you add counts instead of taking a minimum. Loop order matters too: it can distinguish combinations from different orderings of the same coins.

Practice by first stating whether the task asks for a minimum, a count, or reachability. That one distinction changes the state’s meaning and the recurrence.

4. Longest Increasing Subsequence: Learn to track sequence progress

The Longest Increasing Subsequence problem asks for the length of the longest strictly increasing subsequence. The chosen values must stay in their original order, but they don’t need to sit next to each other.

For the list [10, 9, 2, 5, 3, 7, 101, 18], one valid answer is [2, 3, 7, 101], with length four. Define dp[i] as the length of the longest increasing subsequence that ends at index i. Start each position at one, since a single value is a subsequence by itself.

For each earlier index j, check whether nums[j] < nums[i]. If so, the sequence ending at j can extend to i, giving a candidate length of dp[j] + 1. Keep the largest candidate. The answer is the largest state, because the best subsequence can end anywhere.

This direct solution takes O(n²) time and O(n) space. It’s often the right version to explain first because its state and transition are easy to defend. A common follow-up asks for O(n log n). That version maintains tail values and uses binary search to find where each number can improve a tail. The tails help find the length, but they aren’t automatically the final subsequence itself.

That distinction makes a strong interview follow-up: explain what the faster method tracks, then say whether the interviewer wants only the length or also the sequence.

Use the quadratic version to make the dependency visible. Optimize only after you can state why the faster method preserves the answer.

5. Longest Common Subsequence: Handle two-dimensional DP states

Longest Common Subsequence, or LCS, asks for the longest sequence shared by two strings while keeping the character order. Matching characters don’t have to be adjacent. For "ABCD" and "ACDF", the answer is "ACD".

Use dp[i][j] for the LCS length of the first i characters of one string and the first j characters of the other. If the next characters match, add one to the diagonal state: dp[i][j] = dp[i - 1][j - 1] + 1. If they differ, carry the better result from dropping one character from either string.

That gives the mismatch rule dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]). The first row and first column are zero because an empty string has no shared characters.

If the strings have lengths m and n, the basic table takes O(m × n) time and O(m × n) space. If you only need the length, each row depends on the previous row, so rolling rows reduce space to O(min(m, n)). If you need to return the actual sequence, keep enough information to trace the choices back through the table.

LCS gives you a useful test of state design. Each index must represent a prefix, not a character in isolation. Mixing those meanings is a common source of off-by-one errors.

Compare the five questions by pattern, state, and complexity

These five problems share a DP foundation, but the shape of the state tells you what to track. Use this table to pick a next practice problem based on the pattern you need to explain.

For a broader pattern map, Phantom Code AI’s dynamic programming interview pattern notes group common problems by state shape. Use that view to choose a new problem after you can explain the five recurrences here.

When you compare solutions, ask what each state means before comparing code. Then check whether the transition covers every legal choice. That habit catches more errors than jumping straight to a complexity estimate.

Phantom Code AI is an interview assistant that listens, transcribes, recognizes problem types, and gives real-time guidance during mock or live technical interviews. It can be relevant when you want to practice explaining a recurrence out loud, not only submit code. New accounts get free credits at signup without a card.

Frequently asked questions

How do I start solving a dynamic programming problem?

Start by defining one state in plain language. For example, say “dp[i] is the best total through house i.” Then identify the choices that reach that state and write the recurrence. Set the base cases before coding. If you can’t explain what a table entry means, simplify the state before moving on.

Should I use top-down or bottom-up DP in an interview?

Either approach works when it computes the right states. Top-down recursion with memoization can make a recurrence easier to express. Bottom-up tabulation avoids recursive calls and can make space optimization clearer. Start with the form that helps you explain the dependency, then switch if input size or stack use makes it a poor fit.

What is the difference between a subsequence and a substring?

A subsequence keeps the original order but may skip elements. A substring must use adjacent characters. In LCS, the shared characters may have gaps. In a longest common substring problem, they must form one continuous run. Clarify that word early because it changes the state and recurrence.

How many dynamic programming problems should I practice?

Practice enough to explain different state shapes, rather than repeating one pattern many times. Start with one-dimensional choices, then try an amount-based problem and a two-string problem. After each solution, restate the state, recurrence, base case, and complexity without looking at your code.

Conclusion

Work through these five problems in order, and explain each state before you code. When you can derive the recurrence without notes, try a timed mock round. Phantom Code AI can provide real-time guidance during mock or live technical interviews, and its free signup credits let you try it without a card.