DP State Definition
The DP state is the minimum set of parameters that uniquely determines the value of a subproblem. Defining it correctly is the crux of every DP solution.
DP state = your GPS coordinates. Too few dimensions (just latitude) and you can't navigate. Too many (latitude + longitude + altitude + shoe color) and you'll never finish computing routes. Capture exactly what you need to decide the next turn.
Ask three questions: (1) What am I optimizing? (2) What changes as I make decisions? (3) What do I need to know to make future decisions optimally? The answers define your state. Common states: index into an array, remaining capacity, current character, last choice made. The number of distinct states times the cost per state = total time complexity.
Over-specified state: you carry more info than needed, so you have more states than necessary — exponential blowup. Under-specified state: two different situations map to the same state but have different optimal futures — incorrect results. Example of under-specification: in house robber with cooldown, if state is only 'current index', you can't distinguish 'just robbed' from 'can rob now' — you need to add a 'last action' dimension. Bitmask DP encodes subsets in an integer — exponential states but often necessary for NP-hard problems with small n (e.g., TSP for n ≤ 20).
I define the DP state explicitly before writing any code. I ask: what is dp[i][j][k] and what does it represent? Then I write the recurrence as 'dp[state] = some combination of smaller states'. If I find myself needing a variable not in my state to compute the recurrence, I add it to the state. I also estimate state count × work per state = total complexity upfront, to verify it's feasible before implementing.
Adding unnecessary dimensions to the state space 'to be safe' turns a polynomial solution exponential. Be minimal. Conversely, if your recurrence needs a variable that's not in the state, your state is incomplete — adding dimensions is necessary in that case, not a sign of over-engineering.