Dynamic Programming Interview Questions and Answers

Dynamic programming is the topic candidates fear most in a coding interview, and it's usually the one that decides the round. The good news: DP problems are more pattern than genius. Once you can spot the structure and reach for a repeatable framework, most of them collapse into the same handful of moves.

This guide covers the dynamic programming interview questions that come up most, with answers you can actually explain out loud:

• What DP is, and the two properties every DP problem has
• Memoization vs tabulation — the two ways to write the same solution
• A five-step framework for turning any DP prompt into working code
• Worked solutions for the classics: knapsack, longest increasing subsequence, edit distance, coin change, and longest common subsequence
• How to recognize a DP problem before you waste 20 minutes on the wrong approach

What Dynamic Programming Actually Is

Dynamic programming is a method for solving a problem by breaking it into smaller subproblems, solving each subproblem once, and reusing those answers instead of recomputing them. The term was coined by Richard Bellman in the 1950s. In an interview, you don't need the history — you need to recognize when it applies.

A problem is a DP problem when it has both of these:

• Optimal substructure — the best answer to the whole problem is built from the best answers to its subproblems. If you can solve the pieces optimally and combine them, you have optimal substructure.
• Overlapping subproblems — the same subproblems get solved over and over. Naive Fibonacci is the textbook case: computing fib(43) recomputes fib(41) many times across different branches. DP saves each result once.

If a problem has optimal substructure but the subproblems never repeat, it's a divide-and-conquer problem (like merge sort), not DP. If subproblems overlap but there's no optimal-choice structure, it might be plain memoized recursion. DP needs both.

The one-line pitch to give an interviewer: "This looks like DP because the answer to the full problem depends on optimal answers to smaller versions of the same problem, and those smaller problems repeat — so I'll define a state, write a recurrence, and cache results."

Memoization vs Tabulation: Two Ways to Write the Same Thing

Every DP solution can be written top-down or bottom-up. They compute the same answer with the same time complexity. The difference is direction and mechanics, and interviewers often ask you to convert one to the other.

Memoization (top-down): Write the natural recursion, then cache each result in a hash map or array so you never solve the same state twice. This is memoization — recursion plus a lookup table. It's the easier one to reach in a live interview because it mirrors how you'd describe the problem.

Tabulation (bottom-up): Solve the smallest subproblems first and fill a table iteratively until you reach the full problem. No recursion, no stack overflow risk, and it's usually easier to optimize the space down (often to one or two rows).

Here's the same Fibonacci both ways:

# Memoization (top-down)
def fib(n, memo={}):
    if n < 2:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

# Tabulation (bottom-up)
def fib(n):
    if n < 2:
        return n
    dp = [0, 1]
    for i in range(2, n + 1):
        dp.append(dp[i - 1] + dp[i - 2])
    return dp[n]

A strong interview move: write the memoized version first because it's faster to get correct, then say "I can convert this to bottom-up to avoid recursion depth and optimize space" — and do it if there's time.

A Framework for Solving Any DP Problem

When a DP problem appears, don't jump to code. Run these five steps out loud. Interviewers grade the process as much as the answer.

1. Define the state. What does dp[i] (or dp[i][j]) *mean*? This is the hardest and most important step. State the definition in one sentence: "dp[i] is the length of the longest increasing subsequence ending at index i." If you can't define the state cleanly, you don't understand the problem yet.
2. Write the recurrence. How does the answer for one state depend on smaller states? This is the transition. "dp[i] = max(dp[j] + 1) for every j < i where nums[j] < nums[i]."
3. Set the base cases. The smallest states you can answer directly — usually the empty case or a single element.
4. Decide the order. Bottom-up: which states must be filled before others? Top-down: just recurse and cache.
5. Find the answer in the table. The final answer is sometimes dp[n], sometimes the max over the whole table. Say which.

Practicing this framework matters more than memorizing solutions, because it's what transfers to a problem you've never seen. Most technical rounds test whether you can reason through an unfamiliar prompt, not whether you recognize a memorized one. For the broader context of how DP fits into a full loop, see our guide to coding interview questions.

Classic DP Interview Questions, Solved

These five show up across nearly every FAANG-style loop. Learn the state and recurrence for each and you'll recognize their variants instantly.

0/1 Knapsack

Given items with weights and values and a capacity W, maximize total value without exceeding capacity — each item taken at most once. The knapsack problem is the ancestor of a huge family of "choose a subset under a constraint" problems.

• State: dp[i][w] = max value using the first i items with capacity w.
• Recurrence: dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i]) — skip the item, or take it.
• Complexity: O(n·W) time and space; space rolls down to O(W).

Recognizing knapsack is the key skill: subset selection, a capacity limit, maximize or minimize a value. Partition-equal-subset-sum and target-sum are knapsack in disguise.

Longest Increasing Subsequence

Find the length of the longest strictly increasing subsequence in an array. The longest increasing subsequence problem has a clean O(n²) DP and a slicker O(n log n) version with binary search.

• State: dp[i] = length of the LIS ending at index i.
• Recurrence: dp[i] = 1 + max(dp[j]) for all j < i with nums[j] < nums[i].
• Answer: the max over the whole dp array — not dp[n-1], a classic trap.

Edit Distance

Given two strings, find the minimum number of insertions, deletions, or substitutions to turn one into the other. Edit distance (Levenshtein distance) is a two-dimensional string DP and a frequent hard-tier question.

• State: dp[i][j] = edit distance between the first i chars of word1 and first j chars of word2.
• Recurrence: if the characters match, dp[i][j] = dp[i-1][j-1]; otherwise dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) — delete, insert, or replace.
• Complexity: O(n·m) time and space.

Coin Change

Given coin denominations and a target amount, find the fewest coins that sum to the amount (or report it's impossible). This is the change-making problem, an unbounded knapsack variant since each coin can be reused.

• State: dp[a] = minimum coins needed to make amount a.
• Recurrence: dp[a] = min(dp[a - c] + 1) over every coin c ≤ a.
• Base case: dp[0] = 0; initialize the rest to infinity so unreachable amounts stay unreachable.

Longest Common Subsequence

Given two strings, find the length of the longest subsequence present in both (characters in order but not necessarily contiguous). The longest common subsequence problem underpins diff tools and DNA alignment.

• State: dp[i][j] = LCS length of the first i chars of text1 and first j chars of text2.
• Recurrence: if text1[i] == text2[j], dp[i][j] = dp[i-1][j-1] + 1; otherwise dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
• Complexity: O(n·m) time; space rolls down to O(min(n, m)).

How to Recognize a DP Problem in the Room

You won't be told "this is dynamic programming." Watch for these signals in the prompt:

• It asks for a maximum, minimum, longest, shortest, or count of ways — optimization or counting.
• You're making a sequence of choices, and each choice affects what's available next (take/skip, use this coin, match this character).
• A greedy approach gives a wrong answer on some case, but the problem still has clear subproblems.
• The brute-force solution is exponential and recomputes the same states.

When two or three of these line up, define a state and test whether the recurrence holds. If it does, you're in DP territory. This kind of structured recognition is exactly what separates a passing round from a stall, and it's the same muscle tested by broader technical interview questions and role-specific loops for a software engineer. DP and system design interview questions together form the core of most senior engineering evaluations.

Frequently Asked Questions

What is the difference between memoization and tabulation? Memoization is top-down: write the recursion and cache results as you go. Tabulation is bottom-up: fill a table iteratively from the smallest subproblems. Both have the same time complexity; tabulation avoids recursion depth limits and is usually easier to optimize for space.

How do I know if a problem is a dynamic programming problem? Check for two properties: optimal substructure (the best full answer is built from best sub-answers) and overlapping subproblems (the same sub-answers get reused). Prompts asking for a max, min, longest, count of ways, or a sequence of choices are strong signals.

What are the most common DP interview questions? Knapsack, longest increasing subsequence, edit distance, coin change, and longest common subsequence are the recurring classics. Learn the state definition and recurrence for each, and you'll recognize most variants on sight.

Should I write memoization or tabulation in an interview? Start with memoization — it's faster to get correct because it mirrors the recursion. Then tell the interviewer you can convert it to bottom-up to remove recursion depth risk and optimize space, and do so if time allows.

How much DP practice do I need before an interview? Aim to solve the five classic patterns above until you can define their states from memory, then practice recognizing which pattern a new prompt fits. Pattern recognition matters more than raw problem count.

Getting to the Interview in the First Place

Nailing dynamic programming gets you through the technical round — but only if you reach it. The fastest path to that interview is rarely the apply button; it's a short conversation with the engineer or hiring manager on the other side. Articuler helps jobseekers find the actual person hiring for a role using semantic search across 980M+ profiles, then drafts a personalized note that gets roughly 8x the reply rate of a generic cold email — and builds a Playbook so you walk in prepared for that specific team, not a generic loop.