Before writing code, say the state in words and the transition as a formula. If you cannot describe the state in one sentence that the transition depends on, the recurrence is not finished, and no amount of memoization will fix it.
A five-step method for any DP question
MIT's 6.006 course teaches recursive design with the SRTBOT checklist: subproblem definition, relating subproblems recursively, a topological order, base cases, the original problem, and time analysis. The interview version below is the same idea with plainer names. Dynamic programming applies when the recursive solution's subproblems overlap, so the same state would otherwise be computed many times. If subproblems never repeat, plain recursion or divide and conquer is enough.
The time cost of a DP is the number of states times the work per transition. Coin change with amount A and c coin types has A + 1 states and c choices for each, so it runs in O(A·c). Writing that product also exposes a bad state: if the state includes something like the full list of items used so far, the state count is exponential and the memo will not save you.
| Step | Question to answer | Coin change |
|---|---|---|
| State | What does dp[x] mean, in words? | Fewest coins summing to x |
| Transition | How does a state use smaller ones? | dp[x] = 1 + min(dp[x − c]) |
| Base case | Which states need no recursion? | dp[0] = 0; no option means impossible |
| Order | What must be solved first? | Smaller amounts before larger ones |
| Answer | Which state is the original question? | dp[A], or −1 if impossible |
Top-down: coin change with memoization
Top-down means writing the recurrence as a recursive function and caching each result. The documentation describes functools.cache as an unbounded cache equivalent to lru_cache(maxsize=None), and the cached function's arguments must be hashable, which is one more reason to keep the state a small integer rather than a list. Infinity marks impossible states and keeps min() simple: one plus infinity is still infinity, and the wrapper turns it into −1.
The script prints states cached: 12 and then 3 for amount 11 (5 + 5 + 1), then states cached: 2 and -1 for coins [2] and amount 3, where only states 3 and 1 are ever reached. Solving only reachable states is the main advantage of top-down. The third call shows the main cost: amount 5,000 recurses one level per unit and raises RecursionError, because the default recursion limit was 1,000 frames in both the 3.12 and 3.14 builds used here.
from functools import cache
def min_coins(coins, amount):
@cache
def best(rem): # state: fewest coins that sum to rem
if rem == 0:
return 0 # base case
options = [best(rem - c) + 1 for c in coins if c <= rem]
return min(options, default=float("inf")) # inf = impossible
result = best(amount)
print("states cached:", best.cache_info().currsize)
return -1 if result == float("inf") else result
print(min_coins([1, 2, 5], 11))
print(min_coins([2], 3))
try:
min_coins([1, 2, 5], 5000)
except RecursionError as e:
print("RecursionError:", e)Bottom-up: the same recurrence as a table
Bottom-up fills states in an order where every dependency is already computed. For coin change that order is increasing amount, because dp[a] depends only on dp[a − c] for positive coin values c. There is no recursion, so amount 5,000 works and prints 1000. The sentinel amount + 1 stands for impossible: with coins of value at least 1, no valid answer uses more than amount coins.
The last line is the interview classic. Coins [1, 3, 4] and amount 6 print 2 (3 + 3), while the habit of taking the largest coin first gives 4 + 1 + 1, three coins. Greedy is correct for some coin systems and wrong for others, which is exactly why the general problem needs DP. Offer the counterexample before the interviewer asks for it.
def min_coins_table(coins, amount):
impossible = amount + 1 # more coins than ever needed
dp = [0] + [impossible] * amount # dp[a]: fewest coins summing to a
for a in range(1, amount + 1): # order: every a - c is done
for c in coins:
if c <= a and dp[a - c] + 1 < dp[a]:
dp[a] = dp[a - c] + 1 # transition: last coin is c
return dp[amount] if dp[amount] != impossible else -1
print(min_coins_table([1, 2, 5], 11))
print(min_coins_table([2], 3))
print(min_coins_table([1, 2, 5], 5000))
print(min_coins_table([1, 3, 4], 6)) # greedy 4+1+1 uses 3 coins| Concern | Top-down (memo) | Bottom-up (table) |
|---|---|---|
| States computed | Only reachable ones | All of them |
| Recursion depth | Can hit the limit | None |
| Space optimization | Hard to apply | Often one or two rows |
| Writing it first | Mirrors the recurrence | Needs an explicit order |
0/1 knapsack: why the loop direction matters
The two-dimensional recurrence is best[i][c] = max(best[i − 1][c], best[i − 1][c − w] + v): skip item i, or take it once. Each row depends only on the previous row, so a single array of length capacity + 1 is enough. The catch is order. Iterating capacity downward means dp[c − w] still holds the previous row's value when you read it, so every item is used at most once.
The script prints 35, then 60. With weights [1, 3, 4], values [15, 20, 30], and capacity 4, the 0/1 answer takes the weight-1 and weight-3 items. Iterating upward reads a dp[c − w] that already includes the current item, so the weight-1 item is taken four times for 60. That is the right answer to the unbounded knapsack and a wrong answer here. Interviewers ask about this direction on purpose.
def knapsack(weights, values, cap, downward=True):
dp = [0] * (cap + 1) # dp[c]: best value within capacity c
for w, v in zip(weights, values):
caps = range(cap, w - 1, -1) if downward else range(w, cap + 1)
for c in caps:
dp[c] = max(dp[c], dp[c - w] + v)
return dp[cap]
w, v = [1, 3, 4], [15, 20, 30]
print(knapsack(w, v, 4)) # 0/1: each item at most once
print(knapsack(w, v, 4, downward=False)) # wrong for 0/1: reuses itemsLongest common subsequence and the two-row trick
For strings a and b, let L[i][j] be the LCS length of the first i characters of a and the first j of b. If those characters match, L[i][j] = L[i − 1][j − 1] + 1; otherwise it is the larger of L[i − 1][j] and L[i][j − 1]. The full table costs O(m·n) time and space, and the standard way to reconstruct the subsequence itself walks back through it.
Each row reads only the previous row and itself, so two rows suffice, and swapping the strings makes each row as long as the shorter one: O(min(m, n)) extra space. The script prints 4 for ABCBDAB and BDCABA, 5 for interview and review (eview is one such subsequence), and 0 for strings with no shared characters. The trade-off: with two rows you can report the length but cannot walk back to recover the subsequence.
def lcs_length(a, b):
if len(a) < len(b):
a, b = b, a # row length = shorter string
prev = [0] * (len(b) + 1) # row for the previous char of a
for ch in a:
cur = [0]
for j, other in enumerate(b, 1):
if ch == other:
cur.append(prev[j - 1] + 1)
else:
cur.append(max(prev[j], cur[j - 1]))
prev = cur
return prev[-1]
print(lcs_length("ABCBDAB", "BDCABA"))
print(lcs_length("interview", "review"))
print(lcs_length("abc", "xyz"))How to talk through a DP problem aloud
Interviewers grade the reasoning as much as the code, so narrate in the order of the method. Start from brute force: “Each amount can end with any coin, which gives a recursion with repeated subproblems.” Then name the state and transition, state the base cases, and give the complexity as states times transition cost. Only then choose top-down or bottom-up and say why: top-down is quicker to write, bottom-up avoids depth limits and enables row compression.
If you get stuck, shrink the input and fill the table by hand for three or four states; the transition usually becomes visible. These mistakes cost the most points:
- A vague state, such as “dp[i] is the answer up to i,” without saying which answer.
- A base case of 0 where impossible states need infinity.
- An iteration order that reads a state before it is final, as in the upward knapsack loop.
- Passing a list to a cached function, which fails because lists are unhashable.
- Forgetting reconstruction: keep the full table or parent pointers when the path is needed.
A practice list for dynamic programming interviews
Group practice by state shape rather than by problem name. One index over a prefix: climbing stairs, house robber, coin change. Two indices over two sequences: LCS, edit distance. Item and capacity: 0/1 knapsack, partition equal subset sum. Interval states: palindrome partitioning, burst balloons. For each, write the five steps before coding, and solve at least one problem both top-down and bottom-up.
The data structures and algorithms set and the 30-day plan place DP in a wider schedule. A spaced-repetition app such as RecallDeck can help you review the state definitions between practice sessions.
Quick answers
Frequently asked questions
How do I know a problem needs dynamic programming?
Look for optimization or counting over choices (minimum, maximum, number of ways) where a brute-force recursion revisits the same arguments. Draw the first levels of the recursion tree; if identical calls appear, memoizing them is the start of a DP solution.
Is memoization the same as dynamic programming?
Memoization is the top-down way to implement it: recursion plus a cache. Tabulation is the bottom-up way. Both rest on the same recurrence and state space, so they usually share the same time complexity and differ in stack use and which states get computed.
Greedy or DP: how do I decide?
Try to break the greedy rule with a small counterexample, such as coins [1, 3, 4] for amount 6. If greedy survives and you can argue why it is safe, use it. If a counterexample exists, the problem needs to explore choices, which is where DP comes in.
Should I start top-down or bottom-up in an interview?
Top-down is usually faster to write correctly because it mirrors the recurrence you just explained. Convert to bottom-up if the interviewer asks about recursion depth or memory, or if the follow-up is a space optimization such as the one-row knapsack.
Source notes
References and review policy
Information checked on November 7, 2026. Section links identify sources for factual claims and technical explanations. Interpretations, practice scenarios and preparation recommendations are RecallDeck’s editorial work.
From reading to recall
Practice the full interview loop.
RecallDeck schedules the concepts you miss and keeps coding, design, and behavioral fundamentals available when the interviewer changes direction.