Algorithms / Dp State Design
Least You Need to Know: Dynamic Programming State Design
Dynamic programming starts by choosing a state that remembers exactly the information a smaller subproblem needs. Good state design is usually the difference between a clean recurrence and a confused one.
Least you need to know
- A DP state should capture the smallest subproblem that still contains all information needed for future decisions.
- Common state dimensions include an index, a remaining capacity, a current sum, or a boundary like
i..j. - Base cases describe the smallest states whose answers are known immediately.
- If two future situations behave differently, the state must distinguish them.
- Overly large state definitions are inefficient; overly small ones are incorrect.
Key notation
- dp[i] — answer for subproblem ending at or starting from index i
- dp[r][c] — answer for the subproblem at grid cell (r,c)
- state — minimal information needed to describe a subproblem
Worked example
- In the climb-stairs problem, a natural state is
dp[i] = number of ways to reach step i. - The next move comes from step
i-1ori-2. - That gives the recurrence
dp[i] = dp[i-1] + dp[i-2]. - The good state uses just the step index because no other history matters.
Common mistakes
- Students often include unnecessary history in the state even when future choices do not depend on it.
- Students often forget that the base cases are part of the state design, not an afterthought.
- Students often choose a state that cannot distinguish two future situations that behave differently.
How to recognize it
- Ask what the next decision depends on and keep only that information.
- If two partial solutions would branch differently later, the state must separate them.
- Try to name the answer to one subproblem in a short sentence like “best value using the first i items.”
Next recommended lesson
Continue through this topic with Least You Need to Know: DP as a Subproblem Graph.
Least You Need to Know: DP as a Subproblem GraphRelated lessons
Keep going with nearby lessons in the same topic.