Recursion & DP Target: 15s
Top-down is easier to write and debug. Bottom-up avoids stack overflow and is faster. Know both, convert between them.
TOP-DOWN (memoization) BOTTOM-UP (tabulation)
───────────────────── ──────────────────────
+ Natural recursive thinking + No recursion stack limit
+ Only computes needed states + Often cache-friendly
- Python recursion limit - Must fill entire table
- Stack overhead - Must figure iteration order
CONVERSION STEPS:
Top-down → Bottom-up:
1. Identify base cases → fill dp table edges
2. Reverse recursion → forward iteration
3. memo dict → dp array
Bottom-up → Space-optimized:
1. Check: does dp[i] only depend on dp[i-1]?
2. Yes → keep only prev row/value
3. Two rows → rolling array
Rule: start top-down for correctness,
convert to bottom-up if perf matters.Type it from memory. Go.