state 7 of 32 · 5 min
Writing the recursive version first
The fastest reliable way to a correct dynamic programming solution is to write the plain recursion, check it on small inputs, then add three lines.
The sequence
def solve(i, capacity):
if i == len(items):
return 0
best = solve(i + 1, capacity) # skip
w, v = items[i]
if w <= capacity:
best = max(best, v + solve(i + 1, capacity - w)) # take
return bestCorrect and exponential. Now memoise:
from functools import lru_cache
@lru_cache(maxsize=None)
def solve(i, capacity):
...unchanged...One decorator. In Java or C++ it is a map or array lookup at the top and a store before each return, which is three lines rather than one.
Why this order is worth following
The recursion is the place your reasoning is visible. If it is wrong, it is wrong in a way you can trace on a small input. A table filled by the same wrong logic is a grid of numbers with no way to see where the error entered.
It also makes the state explicit. The memo key is exactly the function arguments, so if the arguments are not sufficient the recursion is already wrong and you find out before building anything.
The key must be the whole state
@lru_cache(maxsize=None)
def solve(i, capacity, taken): # taken is a set: unhashable, and enormousTwo failures at once. The arguments must be hashable, and anything exponential in the key means no state ever repeats and the memo is useless.
A memo keyed on less than the state is worse: it returns an answer computed for a different situation, silently.
What to watch
Recursion depth. A chain of 100,000 states overflows the stack. Python's default limit is 1,000. This is the main reason to convert to a loop.
Mutable arguments. Anything that changes cannot be a key.
Global state. A function reading a global that changes is not a pure function of its arguments, so caching it is wrong.
When to stop there
Memoised recursion is often the final answer, not a step. It is easier to read, it computes only the states actually reached, and for sparse state spaces it is strictly better than a table.
Convert to bottom up when the depth is a problem, when the constant factor matters, or when you want to roll the table to save space.