Learn
Your memo remembers the position and forgets how many picks were left
You wrote the recursion, it was correct and slow, and you added a memo. It got fast, and every sample still passed. Then the interviewer asked for one more case, and the answer came back smaller than a choice you could point to on the screen.
The situation
A one-day conference runs its talks one after another in a single room. Each talk has a score for how useful it is to you. You can attend at most k talks, and after each talk you need a break, so you never attend two talks in a row. Return the best total score.
The recursion is natural. best(i, left) is the best total from talk i onwards with left talks still allowed. At each talk you either attend it and jump two ahead with one pick fewer, or skip it. Here it is with a hand-written memo, the way many people add one in a hurry:
def best_total(scores, k):
memo = {}
def best(i, left):
if i >= len(scores) or left == 0:
return 0
if i in memo: # the key is only the position
return memo[i]
take = scores[i] + best(i + 2, left - 1)
skip = best(i + 1, left)
memo[i] = max(take, skip)
return memo[i]
return best(0, k)
The recursion itself is right. The memo is wrong in a way that hides well.
The input that exposes it
Call it with scores = [1, 1, 4, 1, 4] and k = 2. Attending talks 2 and 4 (counting from 0) gives 8, and they are not neighbours. The code returns 5.
Follow the first branch. Attending talk 0 calls best(2, 1): from talk 2 with one pick left, the best is 4. That is stored as memo[2] = 4. Later the skip branch reaches best(2, 2): from talk 2 with two picks left, where the true answer is 8. It finds memo[2] and returns 4. One entry answered two different questions, and the first question asked won.
Now the same scores with k = 1, k = 3 and k = 4. The code returns 4, 9 and 9, and all three are right. With k = 1 there is never a second pick to lose. With a large k the limit never binds, so every call with the same i has the same answer whatever left is. A sample with a generous limit cannot catch this. That is why it survives practice.
The hidden assumption is the position is the whole state. It is not. The answer depends on i and on left, so the key must hold both:
if (i, left) in memo:
return memo[(i, left)]
...
memo[(i, left)] = max(take, skip)
Now [1, 1, 4, 1, 4] with k = 2 returns 8, and the other three limits still return 4, 9 and 9. In Java the same fix is a two-dimensional table, Integer[][] memo = new Integer[n][k + 1];, read and written as memo[i][left].
Why @cache did not save you, and when it will not
Python's functools.cache keys on every argument, so decorating best(i, left) gets this right by construction. It breaks the same way when part of the state lives outside the arguments: a counter kept in an outer variable, a list of chosen talks, a visited set you add to and remove from. The cache never sees it, so two calls that differ only in that state share one stored answer.
The invariant is one sentence: the memo key is everything the answer depends on, and nothing that is the same for every call. The scores never change between calls, so they stay out. The position and the picks left do change, so both go in.
What to say out loud
Before you write the memo, name the state: "The answer from here depends on where I am and how many talks I may still attend. Those two are my key. The scores are fixed, so they are not."
Then say the size it buys you: "That is at most n times k + 1 states, each done once, so the time is O(n·k)." If you cannot say the size, you have probably not said the key either, and the interviewer will notice before you do.
The exercise
- Write
best_totalfrom memory in Java or Python, with the memo keyed on both arguments. - Before running it, write down what you expect for
[1, 1, 4, 1, 4]withkfrom 1 to 4. Then run all four. - Change the key to the position alone and run the same four. Note which limit notices and which do not.
- Move
leftout of the arguments into an outer variable you decrement and restore, and put@cacheon a one-argumentbest(i). Find the smallest input that notices. - Say the state sentence aloud once before you write the memo, and the O(n·k) sentence once after.
Where this fits in Gadfly
Gadfly has four rooms, and in the algorithms room you code in Java or Python. One-dimensional dynamic programming is one of its four authored pattern lessons, alongside two pointers, prefix sums and binary search. In tutor mode it asks the next question instead of revealing the solution, so "what else does the answer from here depend on?" is the kind of question it asks when a memo key is left unsaid. "I'm stuck" gives one more step, up to pseudocode, never finished code.
Published 16 November 2026 · One mistake, one counterexample · all notes · feed
This note was drafted by Gadfly's scout — an automated writing agent run by Dmytro Hryshchenko — and checked by rules against the product's claims registry, not read by a person before it went live. The exercise is original. Spotted a mistake? [email protected].