A battery-dispatch DP indexed only by interval gives wrong answers — which state dimension is missing?

## What a DP state actually has to be A state is a **summary of the past that makes the future independent of how you got there**. Once you are in a state, the set of legal next actions and their consequences must be fully determined by that state and the remaining input — never by history the state has thrown away. Every missing-dimension bug is a violation of exactly that sentence. Take a battery-dispatch planner over a day sliced into intervals `1..n`. During any interval you may charge (paying `c[i]`), discharge (earning `r[i]`), or idle. The battery holds at most one charge, and after discharging, the hardware requires one full idle interval before charging again. Maximise total value. The attractive first draft indexes only by interval: ``` best[i] = max(best[i-1], best[i-2] - c[i-1] + r[i]) ``` Read it carefully and the modelling error is visible. The second term is the only one that ever earns anything, and it hard-codes a single shape: charge in the interval immediately before discharging. A plan that charges cheaply in the morning and holds until the evening peak is not expressible. Worse, the `best[i-2]` term does not actually enforce the cooldown, because the plan summarised by `best[i-2]` may itself have ended with a discharge at interval `i-2`, and charging at `i-1` right after it is illegal. Both failures have one cause: **the cell `best[i]` merges two histories with different futures.** One reached interval `i` empty and free to charge; another reached it holding a charge; another just discharged and must idle. They are not interchangeable, so they cannot share a cell. ## Adding the dimension Enumerate the situations the rules actually distinguish, and give each a name: - `empty` — no charge stored, free to act. - `holding` — a charge is stored, waiting to be sold. - `cooling` — discharged during this interval, so the next interval must be idle. That yields `dp[i][s]` with three values of `s` and one transition per legal move: ``` dp[i][empty] = max(dp[i-1][empty], dp[i-1][cooling]) dp[i][holding] = max(dp[i-1][holding], dp[i-1][empty] - c[i]) dp[i][cooling] = dp[i-1][holding] + r[i] answer = max(dp[n][empty], dp[n][cooling]) ``` Each line reads as a sentence. You are empty at `i` if you were empty and idled, or you were cooling at `i-1` and have now served the mandatory idle interval — which is precisely why a charge cannot follow a discharge immediately, since `holding` at `i` is only reachable from `empty` at `i-1`. Base case: `dp[0][empty] = 0`, the other two seeded with a sentinel so unreachable situations never win a maximum. The state count went from `n` to `3n`, transitions stay constant-work, and the model is now correct for plans of any shape — including holding a charge across dozens of intervals, which the one-dimensional sketch could not represent at all. ## Why this bug survives testing On a two- or three-interval example, charge-immediately-then-discharge *is* the optimal plan, so the broken table agrees with hand calculation and with brute force. The disagreement only appears when the profitable plan requires holding across intervals or when the cooldown genuinely binds. Random tiny inputs are therefore the worst possible test for this class of defect: they are exactly the inputs on which the missing dimension does not matter. Generate inputs shaped to force the rule — a cheap early interval and an expensive late one, or two attractive discharges back to back — and compare against exhaustive enumeration. ## The two directions of state-design error Missing dimensions and surplus dimensions fail differently, and the difference is worth naming: - **Too few dimensions** merges histories with different futures. The symptom is a *wrong answer* that looks plausible and often passes small cases. This is the dangerous one, because the code runs. - **Too many dimensions** splits identical subproblems into duplicates. The symptom is *cost*: more cells, more memory, more time, and often a table that is mostly unreachable. The answers stay correct. This asymmetry is why "when unsure, add a dimension" is bad advice dressed as caution. It is not free, and it does not diagnose anything — a dimension added without a stated meaning just hides the modelling question you have not answered yet. ## Recognising it in an interview When a rule in the problem statement refers to *what happened before* — a cooldown, a limit on consecutive actions, a resource you are carrying, a mode you are in — that rule is naming a dimension. Say so out loud: "the rules distinguish three situations at each interval, so my state is interval plus situation". Then write one transition line per situation and read each aloud as a sentence. A transition you cannot say in words is a transition you have not verified.