In this article
Before you start
This page belongs to the coding interview questions guide, and it assumes you can read short Python.
If you can write a recursive function that adds the numbers in a list, you can follow everything below.
Why interviewers ask this
Interviewers use dynamic programming questions to see whether a candidate can turn a vague "try every option" idea into a precise, fast one. The brute-force answer is usually easy to state. The test is whether you can say exactly what a repeated subproblem is, and prove that there are few of them.
In our question bank, candidates report coding rounds that ask for the number of subsets whose sum exceeds half the total, for wildcard pattern matching with ? and *, and for the best profit with at most two or at most k stock transactions. A weak answer jumps to code and patches it. A strong answer names the state first, writes the recurrence from it, and states the cost as the number of states times the work per state. A Staff-level answer also says when the state space is too large and what to do instead.
Dynamic programming from first principles
- Dynamic programming
- Dynamic programming (DP) is a method for solving a problem that splits into overlapping subproblems with optimal substructure, by solving each distinct subproblem once, storing its result and reusing it. Overlapping means the same subproblem appears many times. Optimal substructure means a best answer is built from best answers to smaller subproblems; for counting and yes-or-no problems, it means an answer that is built from the answers to smaller subproblems. Introduction to Algorithms covers it in a full chapter.
- State
- A state is the smallest set of values that describes one subproblem completely, so two subproblems with equal values must have equal answers. In wildcard matching a state is a pair: how many string characters and how many pattern characters have been used up. Choosing the state is the main design decision in every DP solution.
In plain words
Imagine answering a long list of questions where many questions repeat. A careful person keeps a notebook: before working out an answer, look in the notebook; after working it out, write it down. Dynamic programming is that notebook. The analogy breaks in one place. In DP you must decide what counts as "the same question". The state is that decision. A bad choice writes one question on many pages.
In one precise sentence, DP solves each distinct subproblem once, stores the result under its state, and builds bigger answers from stored smaller ones.
The "ladder" is the order in which to practice. Each rung adds one more value to the state: one number for counting steps, an index and a running total for subsets, two prefix lengths for matching, and a day, a transaction count and a holding flag for stocks. Learn the method on the first rung and every later rung is the same method with a bigger state.
Step 1: Define the state in one sentence
The state of a DP problem is the smallest set of values that makes a subproblem's answer well defined, and you should be able to say it as one sentence before you write any code. The test is a sentence of the form "f(these values) is the best, the count or the yes-or-no answer for this part of the input."
Check the sentence with a second test. If two situations have the same listed values but need different answers, a value is missing. In stock trading, "best profit on day 5" is not enough: the answer differs if you already hold a share, so the state needs a holding flag. If instead two situations with different values always have the same answer, a value is extra and you are creating more states than needed.
For Fibonacci the state is the position n. For subset counting it is the index and the running sum. For wildcard matching it is the two prefix lengths. For stocks it is day, transactions used, holding or not. You now know what to store; the next step says how the stored values connect.
Step 2: Write the recurrence
A recurrence is a rule that computes the answer for one state from the answers of smaller states. You write it by listing the choices available in that state and combining the results of each choice.
Fibonacci has no choice: f(n) = f(n-1) + f(n-2). Subset counting has two choices for each number, skip it or take it, so the count for (i, running) is the sum of the counts for the two next states. Wildcard matching branches on the pattern character, per the problem statement: ? matches any single character, * matches any sequence including the empty one, and the whole string must match. A * therefore has two choices (match nothing, or absorb one more character), while ? or an equal character moves both positions forward by one. Any other character is a failure.
Write the base cases too: the smallest states you can answer without a rule, such as an empty string against an empty pattern. A missing base case is the most common crash.
Step 3: Choose the order: memoize or fill a table
The order of evaluation decides between memoization and a table. Top-down memoization starts at the answer, recurses, and stores each result as it returns. Bottom-up work, called tabulation, fills states from the base cases upward in loops, so every dependency is ready before it is needed.
Both give the same answer, and with the same states and the same work per state they have the same asymptotic time. They differ in what they touch. Memoization computes only the states it reaches, and it keeps your recursive code almost unchanged. Tabulation computes every state in its range, avoids deep recursion, and makes it easy to keep only the previous row to save memory. Python limits recursion depth, so a very deep memoized function can fail where a loop would not.
Pick memoization when you can write the recursion quickly and the states are sparse. Pick a table when the fill order is obvious. Either is acceptable in an interview if you say why.
Step 4: Read the answer and state the cost
The answer is one named state, and the cost is the number of states times the work per state. Say both sentences out loud: "the answer is f of the full input" and "there are this many states, each costing this much."
For the wildcard example below the table has 30 cells and each cell takes constant work, so the cost is proportional to string length times pattern length.1 For Fibonacci with n of 30 there are 31 states and each needs one addition.1 If the cost sentence gives a number you cannot afford, the state is too big or too loose, and you go back to the first step rather than tune the code.
Stating the cost this way is also how you answer the interviewer's inevitable "what is the complexity?" without recomputing under pressure.
Step-by-step description
- Say what one subproblem is.
- Build each state from smaller states.
- Memoize top-down or fill a table.
- Read one named state.
- A state is the smallest set of values that describes one subproblem.
- A recurrence builds each state from smaller states.
- The order of evaluation decides between memoization and a table.
- The answer is one named state.
The diagram holds four facts. A state is the smallest set of values that describes one subproblem. A recurrence builds each state from smaller states. The order of evaluation decides between memoization and a table. The answer is one named state.
Knowing it is half the job. Saying it is the other half.
Interview Clozo is an AI interview copilot for real interview rounds: it hears the question and puts a strong answer on your screen, and you say it in your own words. See the features or how it works.
Start Free Trial →Worked example
Four rungs, each solved with the four steps. All inputs are illustrative and every figure below is computed by the script named in the footnote.1
| Rung | State | States in the example | Cost |
|---|---|---|---|
| 1. Fibonacci | position n | 31 | one addition per state |
| 2. Subset count | index and running sum | 14 | two lookups per state |
| 3. Wildcard match | two prefix lengths | 30 | constant work per cell |
| 4. Stocks, k of 2 | day, transactions used, holding | 48 | a few comparisons per state |
The example state counts are 31, 14, 30 and 48.1
Rung 1, Fibonacci. Naive recursion recomputes the same positions over and over. For n of 30 it makes 2,692,537 calls, while a memoized version runs its body 31 times, once for each state.1 The answer, 832,040, is the same either way.1
Text description of the diagram
- Naive recursive Fibonacci makes 2,692,537 calls for n of 30.
- A memoized version runs 31 times, once for each state.
The chart shows 177 calls at n of 10 and 21,891 at n of 20, against 2,692,537 at n of 30, while the memoized state counts are 11, 21 and 31.1
Rung 2, count subsets above half the total. For the array [1, 3, 4] the total is 8, so a subset must sum to more than 4. Three of the eight subsets qualify: [1, 4], [3, 4] and [1, 3, 4].1 The set [4] sums to exactly 4 and does not count, which is why the comparison is "twice the sum is greater than the total". Counting subsets by sum is the counting form of the 0/1 knapsack problem, where each item is taken or left once; its state is also the item index and the amount used so far.
from functools import cache
def count_big_subsets(nums):
total = sum(nums)
@cache
def go(i, running):
if i == len(nums):
return 1 if running * 2 > total else 0
return go(i + 1, running) + go(i + 1, running + nums[i])
return go(0, 0)The state is (i, running): numbers decided so far and their sum. The recurrence adds the "skip" and "take" branches, and the cache removes repeated pairs. The script also counts by brute force and by a table of ways to reach each sum, and all three agree on 3.1
Rung 3, wildcard matching. Let the string be "adceb" and the pattern *a*b. The state is the pair of prefix lengths, and the answer is whether the full pattern matches the full string.1 For a * the cell is yes if the cell to its left is yes (match nothing) or the cell above is yes (absorb one character). Otherwise a ? or an equal character copies the diagonal cell.
| String prefix | (empty pattern) | * | *a | *a* | *a*b |
|---|---|---|---|---|---|
| (empty) | yes | yes | no | no | no |
| a | no | yes | yes | yes | no |
| ad | no | yes | no | yes | no |
| adc | no | yes | no | yes | no |
| adce | no | yes | no | yes | no |
| adceb | no | yes | no | yes | yes |
The table has 30 cells, one for each pair of prefix lengths from empty up to the full string and pattern. The first column is the empty pattern, which only the empty string matches.1
Rung 4, stocks with at most k transactions. The statements are at most two transactions and at most k transactions. The state is the day, the transactions used and whether you hold a share. For prices 3, 3, 5, 0, 0, 3, 1, 4 and k of 2 that is 48 states.1
def max_profit(k, prices):
hold = [float("-inf")] * (k + 1)
free = [0] * (k + 1)
for p in prices:
for j in range(1, k + 1):
hold[j] = max(hold[j], free[j - 1] - p)
free[j] = max(free[j], hold[j] + p)
return free[k]Here hold[j] is the best profit while holding a share in the j-th transaction, and free[j] is the best profit after at most j sales. The table keeps only the current day, since each day depends on the previous one.
| Transactions allowed | Best profit (illustrative prices) |
|---|---|
| 1 | 4 |
| 2 | 6 |
| 3 | 8 |
| Unlimited | 8 |
The values are 4, 6, 8 and 8 for those four cases.1 With unlimited transactions you do not need the table at all: the unlimited version is solved greedily by adding every rise, and the greedy idea behind it is covered in the greedy ladder.1
Trade-offs and edge cases
Dynamic programming trades memory and a precise state for speed, and it is the wrong tool when a simpler method works or the state cannot be kept small.
Text description of the diagram
- Memoization computes only the states it reaches.
- Tabulation fills every state in its range with loops.
Memoization computes only the states it reaches. Tabulation fills every state in its range with loops. That is the practical difference to mention if asked.
- State too large. In subset counting the running sum is part of the state, so the state count grows with the numeric size of the numbers, not just how many there are. That is fine for small sums and fatal for huge ones. Say so, then consider a different decomposition.
- A greedy rule exists. If one local choice is always safe, as in unlimited-transaction stocks, the table is unnecessary work. Check with a small counterexample before reaching for DP.
- Unhashable arguments. A cached Python function needs hashable arguments, so pass indices or tuples rather than lists.
- Deep recursion. Python caps recursion depth, so switch to a table or raise the limit with undefined when states chain very deep.
- Graph-shaped dependencies. When states depend on each other in a graph rather than a line or grid, you need an order that respects dependencies; see topological sort, and for grid search without an obvious fill order see the grid search ladder. When the task is a direct lookup rather than a choice over subproblems, the hashing and array ladder covers the simpler tools.
How to answer it in an interview
How would you approach a dynamic programming problem you have not seen before?
I start by naming the state in one sentence. For stock trading with limited transactions, that is the best profit on a given day, with a given number of transactions used, while holding a share or not. Then I write the recurrence from the choices in that state, buy, sell or wait. I pick memoization or a table depending on whether the order is obvious. I state the cost as number of states times work per state, and I check a tiny input by hand. If that cost is too big, I look for a smaller state or a greedy rule.
The spoken structure: name the state, give the recurrence, pick the order, state the cost, then say what you would do if the cost is too high.
Common mistakes
- "I'll just add a cache to my recursion." (wrong) A cache only helps if the same arguments recur; with a loose state it stores everything and saves nothing. (right) "I define the state first, then cache on exactly those values."
- "The state is the day." (wrong, for stocks) It ignores whether you hold a share. (right) "The state is day, transactions used and holding or not."
- "Memoization is faster than a table." (wrong) With the same states and work per state their time is the same order. (right) "They differ in recursion depth and in whether unreachable states are computed."
- "Every stock problem needs DP." (wrong) The unlimited-transaction version is greedy. (right) "I check whether a local rule works before building a table."
Follow-up questions
How do you implement wildcard pattern matching with ? and *?
Use a table indexed by how much of the string and how much of the pattern are used. A * takes the left cell or the cell above, a ? or equal character takes the diagonal, and the bottom-right cell is the answer. The cost is proportional to string length times pattern length.
When to buy and sell stocks with at most k transactions?
Track the best profit while holding and while not holding for each transaction count, updating them once per day, as in the code above. In the worked example the profit is 6 for k of 2 and stops rising at 8 once k reaches three.1 For k of 2, counting days from 1, buy at 0 on day 4 and sell at 3 on day 6, then buy at 1 on day 7 and sell at 4 on day 8, for a profit of 6, as in the problem 123 example.
How does this change for a knapsack with a weight limit and a happiness target?
Keep the state as (item index, weight used, happiness reached, capped at the target X) and store the minimum cost that reaches it. Each item is skipped or taken, and the answer is the cheapest state at the target. With a weight limit Y and whole-number weights there are items × (Y+1) × (X+1) states, each with constant work.
How do you know a problem needs dynamic programming?
Look for a brute-force search over choices where the same partial situations recur, and where the overall answer is built from the answers to smaller parts. If you can write a short state sentence and the number of states is small, DP fits.
Should you use memoization or a table in an interview?
Use whichever you can write correctly fastest and explain. Memoization is quicker to write from a recursive idea; a table avoids deep recursion and makes memory savings easy. Say which one you chose and why.
What if the state space is too big?
Say so directly, then try to remove a value from the state, find a monotone or greedy rule, or restructure the problem. Interviewers value the diagnosis as much as the fix.
- A dynamic programming ladder is one four-step method applied to problems whose state grows rung by rung.
- Say the state in one sentence before any code, and test it for a missing or an extra value.
- A recurrence builds each state from smaller states, and base cases anchor it.
- Memoization and tabulation give the same answer; choose by sparsity and recursion depth.
- Cost is the number of states times the work per state; check for a greedy shortcut first.
Sources
- Introduction to Algorithms, fourth edition (chapter on dynamic programming) — MIT Press, 5 Apr 2022
- sys.setrecursionlimit (Python documentation) — Python Software Foundation, 26 Oct 2026
- functools: higher-order functions and operations on callable objects (cache, lru_cache) — Python Software Foundation, 26 Oct 2026
- Wildcard Matching (problem 44) — LeetCode, 26 Oct 2026
- Best Time to Buy and Sell Stock III (problem 123) — LeetCode, 26 Oct 2026
- Best Time to Buy and Sell Stock IV (problem 188) — LeetCode, 26 Oct 2026
- Best Time to Buy and Sell Stock II (problem 122) — LeetCode, 26 Oct 2026
