State Definition & Transition

Getting the state and transition right is the core of every DP solution. A good state makes the recurrence obvious; a bad one leads to dead ends or explosions in time or space. This article focuses on how to define state, how to write transitions from it, and how to fix things when the recurrence doesn’t work.

Why State Comes First

The state is the contract of your DP:

• It defines what one “subproblem” is.
• The transition says how that subproblem is computed from smaller subproblems.
• The final answer is expressed in terms of one or a few state values.

If you define state poorly (too much, too little, or the wrong quantity), you either cannot write a transition or get wrong answers. So the first step is always: write down exactly what dp[...] represents, in one sentence.

What Makes a Good State

A good state is:

1. Unambiguous — One precise meaning. Not “something about the first i elements” but “max profit from houses [0..i] when we are allowed to consider robbing house i” vs “when we do not rob house i” (if you need that distinction).
2. Sufficient — You can compute this state using only smaller states (smaller indices or smaller values). You never need information that isn’t already in the state or in the input.
3. Minimal — You don’t store more than you need. Adding “and whether we took the last element” is only part of the state if the transition actually needs it.
4. Aligned with the answer — The problem’s final answer is either a single state value (e.g. dp[n]) or a simple function of state values (e.g. max(dp[0], …, dp[n-1])).

If your recurrence feels forced or you need “extra” information when computing dp[i], the state is likely wrong or incomplete.

State Shape: One Dimension

For 1D state dp[i], the index usually means one of:

Meaning of i	State meaning	Example
Prefix length	Best answer for the prefix [0..i] (may or may not “use” position i)	House Robber, Climbing Stairs
End position	Best answer for something ending at i (must use i)	LIS length ending at i, max sum subarray ending at i
Value	Answer when the parameter equals i (e.g. amount, capacity)	Coin Change dp[amount], 1D knapsack by capacity

Critical distinction:

• “Prefix” state: The answer for the whole input is often dp[n-1] or dp[n].
• “Ending at i” state: The answer is usually max(dp[0], …, dp[n-1]) (or similar), because the best solution might end at any position.

Choosing “prefix” vs “ending at i” affects both the recurrence and how you combine results. Be explicit in your definition.

State Shape: Two Dimensions

For 2D state dp[i][j], the two indices typically represent:

Context	First index	Second index	Example
Two sequences	Length of first prefix	Length of second prefix	LCS dp[i][j] = LCS of s[0..i), t[0..j)
Grid	Row	Column	Path count / min path sum to (i, j)
Knapsack	“First i items”	Capacity	dp[i][w] = best value with items 0..i-1, capacity w

Conventions that help:

• Prefix length vs 0-based index: Many string DP use “length” so that dp[0][j] and dp[i][0] are empty prefix (base case). Stick to one convention and document it.
• Inclusive vs exclusive: e.g. s[0..i) means indices 0 to i-1. State definition should say whether i is inclusive or exclusive so base cases and transitions are consistent.

Deriving the Transition

Once the state is fixed, the transition answers:

Given dp[state], which decisions or choices lead to this state? What smaller states do we need?

Common patterns:

1. Choice at the current step (take or skip)

• State: e.g. “best value for prefix [0..i]”.
• Transition: We either use element i or we don’t. So we need to express “best if we use i” and “best if we don’t” from smaller states.
• Example (House Robber): dp[i] = max(dp[i-1], nums[i] + dp[i-2]) — skip house i vs take it (then must skip i-1).

2. Extend from a smaller prefix / position

• State: e.g. “best value for something ending at i”.
• Transition: We extend from some smaller j < i that satisfies a constraint (e.g. nums[j] < nums[i] for LIS). So dp[i] = cost(i) + max{ dp[j] : j valid }.
• Example (LIS): dp[i] = 1 + max{ dp[j] : j < i, nums[j] < nums[i] }.

3. Combine two smaller subproblems (2D)

• State: e.g. “answer for prefix s[0..i) and t[0..j)”.
• Transition: Match last characters, or skip one from s, or skip one from t. So we need dp[i-1][j-1], dp[i-1][j], dp[i][j-1].
• Example (LCS): if s[i-1] == t[j-1] then dp[i][j] = 1 + dp[i-1][j-1]; else dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

4. Partition / split

• State: e.g. “best cost for prefix [0..i]”.
• Transition: Split at some k < i: “solve [0..k] and [k+1..i] (or similar)”. So dp[i] = min over k of (dp[k] + cost(k, i)).
• Used in matrix chain, some string segmentation problems.

Rule of thumb: every term in the recurrence must come from a state you already defined. If you find yourself saying “we need to know whether …”, that “whether” might need to be part of the state (e.g. an extra dimension or a different state set).

When the Transition Doesn’t Work

If you can’t write a recurrence, or the recurrence needs information you didn’t store:

1. State too small — You’re missing a dimension or a distinction. Example: “max profit from [0..i]” might need to know “did we take i-1?” so you know if you can take i. Fix: refine state (e.g. dp[i][0] = best without taking i, dp[i][1] = best with taking i) or redefine (e.g. “best for [0..i] given we do not rob house i” vs “we may rob house i”).
2. State too big — You’re storing sets, full sequences, or unbounded history. DP state should be “small”: a few indices or small integers. Fix: find a minimal summary (e.g. “last chosen index” instead of “set of all chosen indices”).
3. Wrong quantity — You’re optimizing or counting the wrong thing. Example: “number of ways to reach i” vs “min cost to reach i”. Fix: re-read the problem and make sure the state quantity matches the question (min/max/count).
4. Wrong order — For 2D, you might be using dp[i+1][j] before it’s computed. Fix: iterate so that every dependency is computed first (usually increase i and j).

Checklist Before Coding

• State definition written in one sentence (what does dp[i] or dp[i][j] mean?).
• Base cases identified (smallest i/j or empty prefix) and set by hand.
• Transition written in math or pseudocode using only smaller indices/values.
• Final answer identified (which cell(s)? max over row?).
• Iteration order decided so dependencies are ready when needed.

Summary

• State = minimal, sufficient information to define one subproblem and to express the transition and the final answer.
• Transition = how to compute the current state from smaller states; it follows from the state definition and the allowed decisions.
• Define state first; if the transition doesn’t fall out naturally, adjust the state (add a dimension, refine the meaning, or change the quantity), then try again.

Once state and transition are clear, base cases and iteration order are mechanical, and you can implement bottom-up or top-down and then optimize space as needed.