Defining the State
The state definition is the most important DP decision: it names exactly what each cached or tabulated answer means.
State Is a Contract
A DP state is not just an array index. It is a contract: dp[i] means a precise answer to a precise smaller question. If that sentence is vague, the transition will be vague too. Strong definitions include the scope, the decision boundary, and the returned quantity.
Compare dp[i] is the answer up to index i with dp[i] is the maximum money robbable from houses 0..i. The second version tells you what choices are legal and which previous states can be used.
Choose Dimensions From What Changes the Future
A dimension belongs in the state if changing it can change the answer to the remaining problem. Index is common because the set of remaining items changes. Capacity is needed in knapsack because the same index with different remaining capacity has different possibilities. Two indices are needed in LCS and Edit Distance because both prefixes matter.
Do not include history just because it happened. Include history only if it affects future choices or scoring. The art is to remember enough for correctness while letting many histories merge into one reusable state.
Common State Patterns
Frequent patterns include:
- Index state: dp[i] is the best or count for a prefix, suffix, or position. Examples: Climbing Stairs, House Robber, Decode Ways.
- Index plus capacity: dp[i][c] is the best using first i items with capacity c. Examples: 0-1 Knapsack, Partition Equal Subset Sum.
- Two indices: dp[i][j] compares or combines two prefixes. Examples: LCS, Edit Distance, Distinct Subsequences.
- Interval: dp[l][r] is the best answer inside a range. Examples: Burst Balloons, Palindrome DPs, Stone Game.
Pitfalls
The first pitfall is defining a state that cannot be transitioned cleanly. If dp[i] says best answer involving index i but does not specify whether i is included, you may need extra cases or a second state.
The second pitfall is mixing prefix and suffix meanings. If dp[i] sometimes means up to i and sometimes starting at i, base cases and loop direction become error-prone. The third pitfall is overfitting to the answer. The answer may be a single value, but intermediate states often need more dimensions to be correct.
A Quick Validation Test
After defining a state, ask three questions. Can I identify the final answer state? Can I express this state using smaller or simpler states? Do the base cases have obvious values?
If any answer is no, revise the state before writing code. Most DP failures come from forcing a transition onto a weak state definition.
Key Takeaways
- A state definition must say exactly what each DP value represents.
- Add dimensions for information that changes future choices or scoring, not for irrelevant history.
- Common patterns include index, index plus capacity, two indices, and interval states.
- Validate a state by checking answer location, transition feasibility, and base cases before coding.