state 3 of 32 · 6 min

Choosing what to remember

Everything else in dynamic programming is mechanical. Choosing the state is the part that decides whether the solution is right, and it is where almost every failure happens.

The definition

A state is a description of a situation complete enough to finish the problem from. The test is one question:

If I told you only this, could you work out the rest correctly?

Applying it

Knapsack, with the state "which item am I at":

code

at item 5, 30 units of room left   -> take the heavy valuable one
at item 5,  2 units of room left   -> cannot

Two situations, same state, different answers. The state is too small, and the missing piece is exactly what distinguishes them: the room remaining.

That is the general method. To test a proposed state, try to construct two histories that arrive at it and disagree about what to do next. If you can, the state is missing whatever separates them.

Too large is a different failure

code

state = (index, capacity, the exact set of items taken)

This is correct and useless. The set of items is exponential, so there are too many states to store and none of them repeat, which destroys the overlapping subproblems the whole method depends on.

A state that is never revisited gives a memo that never hits.

Too small	Too large
Wrong answers	Correct, and too slow
Fast, and confidently wrong	Memo never hits
Two pasts collide	Nothing repeats

Finding the smallest sufficient one

The craft is discarding what no longer matters. For the travelling salesman, the route so far is a permutation, which is enormous. But for deciding what to do next, only two things matter: which cities are done, and where you are standing. The order they were visited in is irrelevant to the future.

code

full history: 15! orderings      ~ 1.3 trillion
(set, position): 2^15 x 15       ~ 500 thousand

Same answers, from noticing what the future does not depend on.

Writing it down

Before any code, write one sentence:

best[i][c] is the most value obtainable from items i onward with c units of room remaining.

That sentence fixes the table size, the loop bounds, the base cases and where the answer lives. Skipping it is why people end up with a filled table and no idea which cell to return.