state 32 of 32 · 6 min
Recognising it under pressure
Interview dynamic programming is rarely a problem you have seen. It is a problem whose shape you recognise, and the recognition is trainable.
The signals
| The question says | Suggests |
|---|---|
| "how many ways" | counting DP, addition |
| "minimum or maximum cost to" | optimising DP |
| "is it possible to" | boolean DP |
| "longest or shortest subsequence" | a sequence DP |
| "you may take or skip each" | take or skip |
| "split into groups" | interval or partition DP |
| "at most k times" | a dimension for k |
| "every arrangement" | backtracking, not DP |
That last row is the distinction worth being sure of. DP computes a value, a count or a best. Producing the actual list of every arrangement is enumeration, and it cannot be memoised because each answer is a distinct object.
The sequence to follow out loud
1. Brute force first. "I can try every subset, that is 2^n." This is not a weak answer. It establishes the problem is understood and gives a baseline to improve.
2. Name the repeated work. "I am solving the same subproblem for different prefixes." That sentence is the reason DP applies, and saying it is what the interviewer is listening for.
3. State the state. One sentence. "best[i][c] is the most value from items i onward with c capacity left."
4. Write the recurrence. The choices at that state.
5. Base cases and the answer cell. Say which cell holds the answer and why.
6. Complexity, from the state. States times work per state.
7. Then code it.
Most candidates go straight to step 7 and get stuck at minute fifteen.
What they are actually assessing
Not whether you have memorised knapsack. Whether you can:
- notice that subproblems repeat
- choose a state and justify it
- say why a greedy rule would fail here
- get the base cases right
- state the complexity without guessing
A candidate who reaches a correct recurrence and runs out of time coding it usually scores better than one who types a memorised solution and cannot explain the state.
If you get stuck
Say where. "I think the state needs to include how many transactions are left, I am working out whether it also needs today's price." That is visible reasoning, and it is what they are trying to observe.
The three worth knowing cold
If time is short, know these completely, because most others are a variation:
Knapsack, take or skip with a capacity. Longest common subsequence, the two sequence grid. Coin change, both the minimum and the counting version, and why the loop order matters.