From Recursion to DP
Most DP solutions begin as a recursive choice model, then become efficient by caching states or by filling them iteratively in dependency order.
Start With the Recursive Question
A clean recursive formulation asks: if I am at this state, what choices can I make next, and what smaller states do those choices produce? This is often easier than jumping straight to an array. For House Robber, from index i you can skip to i + 1 or take house i and jump to i + 2. For Coin Change, from amount a you can choose any coin and continue with a - coin.
The recursive version is valuable because it exposes the state and transition. It may still be too slow, but it tells you what must be cached or tabulated.
Plain Recursion Is a Specification, Not the Final Algorithm
Plain recursion is acceptable as a thinking tool, but repeated states make it inefficient. Once two branches ask for the same state, the recursive tree is doing duplicate work. The state definition tells you the cache key: every argument that changes the answer must be part of the key.
This is the moment recursion becomes DP. You are no longer exploring histories; you are solving unique states. The algorithmic cost becomes the number of states times the cost of evaluating each transition.
The Mechanical Path
The transformation is mechanical:
- Write the recursive function signature so its parameters are exactly the state.
- Add base cases for states whose answers are known immediately.
- Before computing a state, check whether the cache already has its answer.
- Store the computed answer before returning it. This is memoization.
- If desired, reverse the dependency direction and fill a table iteratively. This is tabulation.
Top-down and bottom-up are not different recurrences. They are different evaluation strategies for the same state graph.
Why This Matters for Senior Interviews
Senior interviewers often change constraints mid-problem. If your solution is memorized, a small variant can break it. If your solution came from a recursive model, you can adapt the state and transition.
For example, Climbing Stairs becomes Min Cost Climbing Stairs by changing what the state returns. Coin Change becomes Coin Change II by changing whether the transition minimizes coin count or counts combinations. The recursion-to-DP workflow gives you a reusable reasoning system instead of a catalog of formulas.
Key Takeaways
- Begin with a recursive state question before worrying about arrays.
- The cache key is the set of parameters that uniquely determine the answer.
- Memoization and tabulation usually implement the same recurrence in different orders.
- The cost of a DP is unique states times transition work, not the size of the naive recursion tree.