Define a sufficient DP state
Why you care
Most wrong DP answers are decided before any recurrence exists: the state is missing a variable, so two situations share one cache entry. On the job that is the planner right on a small fixture and wrong at production size, with no error. Interviewers open with "what does your function return, and for which arguments?" because naming a state separates understanding from pattern-matching.
Explain like I'm 5
Halfway through a train journey, a friend asks what the rest will cost. You do not recite every station so far. You say where you are and whether the next ticket has a restriction based on the last. Those two facts are the state. The full diary is history; use it as your notebook key and you never recognise a situation you have already seen.
Core concept
A state is the smallest set of facts that, with the remaining input, fully determines the future. Write it as a sentence: "f(i, last) = ways to fill slots i.. given the previous kind last".
- Overlapping subproblems: different paths reach the same state. If none do, memoisation buys nothing.
- Optimal substructure: the future ignores how you arrived.
- Name the question: feasibility (
or), counting (+) or optimization (min/max); only the combine changes. Say where the answer lives, e.g.f(0, None). - Key every variable a future rule reads, and nothing else.
Use DP when the same sub-situation recurs and a small summary captures the past. Do not use it when a greedy choice is provably safe or the only valid summary is the whole history.
Under the hood
functools.cache and lru_cache store results in a dict keyed by the arguments, so they must be hashable: a list raises TypeError. The docs add that f(a=1, b=2) and f(b=2, a=1) may be separate entries, so pass state positionally.
Minimal example A memo key that forgets one dependency
def brute(n, last=None):
if n == 0: return 1
return sum(brute(n - 1, s) for s in "ABC" if (last, s) != ("A", "C"))
def count(n, last, memo, key):
k = key(n, last)
if k not in memo:
memo[k] = 1 if n == 0 else sum(
count(n - 1, s, memo, key) for s in "ABC" if (last, s) != ("A", "C"))
return memo[k]
print(brute(10))
print(count(10, None, {}, lambda n, last: n))
print(count(10, None, {}, lambda n, last: (n, last)))17711
1536
17711In production One state, three questions, and an honest key
INF = float("inf")
def solve(n, kinds, banned, cost, key_mode="state"):
"""Pick one kind per slot; (prev, next) pairs in `banned` are illegal.
Returns (feasible, count, min_cost, memo_entries). Recursive: keep n below ~900
(default recursion limit 1000; see dsa-07-03)."""
memo = {}
def go(i, last, hist):
k = (i, last) if key_mode == "state" else hist
if k in memo:
return memo[k]
if i == n:
res = (True, 1, 0) # base: nothing left to place
else:
feas, cnt, best = False, 0, INF
for s in kinds:
if (last, s) in banned:
continue
f, c, m = go(i + 1, s, hist + (s,))
if not f:
continue # never add to the INF sentinel
feas, cnt, best = True, cnt + c, min(best, m + cost[s])
res = (feas, cnt, best)
memo[k] = res
return res
return go(0, None, ()) + (len(memo),)
cost = {"A": 3, "B": 1, "C": 2}
banned = {("A", "C"), ("B", "B")}
print(solve(0, "ABC", banned, cost))
print(solve(1, "ABC", banned, cost))
print(solve(12, "ABC", banned, cost))
print(solve(12, "ABC", banned, cost, key_mode="history"))
print(solve(3, "B", {("B", "B")}, {"B": 1}))
print(solve(4, "AB", {(p, q) for p in "AB" for q in "AB"}, {"A": 5, "B": 0}))(True, 1, 0, 1)
(True, 3, 1, 4)
(True, 23427, 18, 37)
(True, 23427, 18, 42212)
(False, 0, inf, 2)
(False, 0, inf, 3)See it happen Two states, one wrong key
- Both memos start empty; the question is how many ways to fill 2 remaining slots.
- A call with 2 slots left after A computes 5 ways (A cannot be followed by C) and stores it.
- A call with 2 slots left after B has 8 ways, but the n-only memo finds key 2 and returns 5.
- The (n, last) memo treats it as a new state and stores 8 beside the 5.
In your world
The situation
A nightly planner schedules 30 days of runs, each FULL (A), DELTA (B) or REPAIR (C); REPAIR may not directly follow FULL. A Jenkins stage prints the number of legal plans to size the QA matrix.
What actually breaks
The memo was keyed on days remaining only. The stage prints 1,610,612,736 and stays green; the true count is 4,052,739,537,881. The matrix is about 2,500 times too small; nothing errors.
What you'd do on Monday
Key on (days_left, last): 31 x 4 states, 3 transitions each, about 370 steps. Add a check comparing the memo with plain recursion at n = 10 (17,711) and fail the build on mismatch.
Imagine you work at LinkedIn
The numbers
Fill 20 slots from 4 types (post, job, ad, suggestion), no two adjacent equal. Histories: 4 x 3^19 = 4,649,045,868. State (slot, last): 20 x 4 = 80 states x 4 transitions = 320 checks. Add "at most 3 ads": (slot, last, ads_used) = 20 x 4 x 4 = 320 states, 1,280 checks.
What the Scenario-A answer does here
The Monday fix, a key of exactly the variables the rules read, still works. What breaks is keying on the partial feed: 4.6 billion entries cannot exist, while the true state is under a thousand.
What flips at this scale
Each new rule asks whether the future reads something not yet in the key. Add that one variable with its smallest range (ads used 0-3, not ad positions); state count multiplies by that range, never by history length.
The trade-off you'd defend
I would defend a small rule-derived state over a history key, trading an hour of thinking per rule for a memo under a thousand entries.
Illustrative; slot count, types and rules are assumptions, not LinkedIn-published. Arithmetic is exact for them.
Gotchas
Key omits a dependency
Memo count 1,536 where brute force gives 17,711, no exception.
States differing in last shared one entry.
List every variable any rule reads and key on all of them; cross-check small n against brute force.
Key stores the whole history
Correct answer but 42,212 memo entries for 12 slots instead of 37.
No two paths share a key, so the cache never hits.
Key on the summary the future reads (state mode in the production block).
Unhashable argument
TypeError: unhashable type: 'list'.
The cache is a dict and a list cannot be a key.
Pass a tuple or an index.
from functools import cache
@cache
def total(xs):
return sum(xs)
try:
total([1, 2])
except TypeError as e:
print("TypeError:", e)
print(total((1, 2)))TypeError: unhashable type: 'list'
3Tricky questions
A maximum with a recursive description means DP.
DP needs overlapping states and a small summary of the past. A provably safe local choice is greedy; with no repeated sub-situation it is a scan.
Scenario question
You're handed a function counting valid weekly schedules, memoised on (day,). It is right for 3 days and wrong for 10. Find the bug and say how you will trust the fix.
Model answer
I list what the validity rule reads: the previous day's mode. It is missing from the key, so I change it to (day, last_mode) and compare against brute force for n up to about 12, plus n = 0. The trade-off is a table four times larger for a correct answer; a smaller wrong table is no optimisation.
Interview corner
CommonWhat does your DP function return, and what are its arguments?
TrickYour memo gives a smaller count than brute force. Where do you look?
Experience checkHave you cached something whose key was incomplete?
Memory hook
The state is the notebook entry that lets the trip planner forget the diary.
Put every variable the future reads in the key and nothing else.
Self-check
What three questions can one state answer?
Feasibility, counting and optimization; only the combine step changes.
Why does keying on the full path defeat memoisation?
No two paths share a key, so there are no hits and entries are exponential.
Which variables belong in the key?
Those the remaining rules read.
Assert brute force equals the (n, last) memo for n = 1..12, then run the n-only key and paste the first n where they differ, plus the 30-day count 4,052,739,537,881.