Writing the Transition
The transition is the recurrence that combines smaller states, usually derived by isolating the last decision or the next decision.
Derive From a Decision Boundary
A transition should come from a crisp decision boundary. The most common approach is the last decision: what was the final move, final item used, final character matched, or final cut made? Climbing Stairs asks whether the last move was one step or two. Edit Distance asks whether the last characters match or which edit operation is last.
For suffix-style recursion, the next decision can be clearer: from this index, do we take, skip, cut, or match? Either direction is fine as long as the resulting states are smaller or closer to a base case.
Choose the Aggregation
The problem goal determines how choices combine. Counting problems usually sum disjoint possibilities. Optimization problems usually take min or max over choices. Feasibility problems often use boolean or across choices and boolean and for required conditions.
Coin Change minimizes one plus the best answer for the remaining amount. Coin Change II counts combinations, so it sums ways while carefully avoiding duplicate orderings. House Robber maximizes between skip and take. Word Break uses whether any valid word leads to a solvable suffix.
Respect Validity Conditions
Every transition needs guards. You can use a coin only if coin <= amount. You can decode two digits only if the value is between 10 and 26. You can move from a grid parent only if the parent is inside bounds and not blocked.
Invalid choices should not quietly contribute zero unless zero is the correct identity. For minimum problems, invalid often means infinity. For maximum problems, invalid may mean negative infinity. For counting, invalid usually contributes zero.
Avoid Double Counting
When summing choices, make sure the groups are disjoint or intentionally ordered. Climbing Stairs groups paths by their last move, so one-step and two-step endings do not overlap. Coin Change II counts combinations, not permutations, so the state includes which coin index is allowed; otherwise the same set of coins can be counted in many orders.
If your count seems too large, inspect whether two transition branches can generate the same final object. If yes, refine the state or constrain the iteration order.
Key Takeaways
- Transitions are easiest to derive from the last decision or next decision.
- Use sum for disjoint counts, min or max for optimization, and boolean logic for feasibility.
- Validity guards are part of the recurrence, not an implementation detail.
- Counting transitions must avoid duplicate generation of the same outcome.