Choosing the state
The state is the smallest description of "where we are" that determines the best way to finish. Get it from the parameters of the brute-force recursion.
What a state is
A state is a description of a subproblem: everything about the situation that the rest of the computation depends on, and nothing more. The DP table has one entry per state, so the state decides both whether the algorithm is correct and how fast it is.
- Too little, and two situations that need different answers share one table entry: the algorithm is wrong.
- Too much, and situations that need the same answer get separate entries: the algorithm is correct but slow, sometimes exponentially.
A procedure for finding it
Finding the state
1. Write the brute-force recursion
- Describe the solution as a sequence of decisions: which coin next, take or skip this item, which character to match.
- Write a function that makes one decision, recurses on what is left, and combines the results (min, max, sum or or).
2. Read off the parameters
- Parameters that change between calls and are read by the function are the state.
- Parameters that never change (the input array, the coin list) are not: they are the same for every subproblem.
3. Check it
- Does the state alone determine the answer for the rest, whatever path led here?
- Count the states: their number times the work per state is the running time.
Worked example: when the obvious state is not enough
"Choose numbers from a list, never two adjacent, to maximise the sum" has the natural state i: the best sum using positions i onwards. Two choices at i (take it and jump to i + 2, or skip to i + 1) and the answer for the rest depends only on i.
Change the rule to "never three in a row". Now, standing at position i, whether you may take it depends on how many of the positions just before it you took. Two paths that both arrive at i, one having taken i − 1 and i − 2 and the other not, need different answers. The state i is missing information.
The brute-force recursion makes this obvious: to decide, the function must be told the length of the current run of taken numbers, so the state is (i, run) with run ∈ {0, 1, 2}. That is 3n states with two choices each, still linear.
| Rule | State | Number of states | Why |
|---|---|---|---|
| no two adjacent | i | n | the past only matters through "was i − 1 taken", which the jump to i + 2 already encodes |
| no three in a row | (i, run) | 3n | whether i may be taken depends on the run so far |
| at most k taken in total | (i, taken) | n(k + 1) | the budget left changes what the future may do |
Whenever an argument is "I need to know something about what happened before", that something belongs in the state. Then count the states before writing any code.