Top-Down (Memoized Recursion)
Usually O(states * transitions), plus recursion overhead
Use When
- State transitions are easier to express recursively
- Only a subset of states is reachable
- You want faster initial implementation and easier debugging
Avoid When
- Deep recursion risks stack overflow
- Runtime overhead of recursive calls is costly
Mental model: Ask for answer to target state; cache everything along the way.
Bottom-Up (Tabulation)
Usually O(states * transitions) with low constant factors
Use When
- State order is clear and iterative loops are straightforward
- Need predictable performance and no recursion stack risk
- Space compression (rolling arrays) is needed
Avoid When
- State space is huge but sparsely reachable
- Dependency ordering is hard to derive
Mental model: Fill table from base cases up to final answer.