patterns
22 min
dp
recursion

Pattern: Recursion & DP

Define state, transition, base cases — then optimize space.

Covers: dp · recursion

The DP interview script 1. **Brute recursion** — what subproblem repeats? 2. **State** — “dp[i] means …” 3. **Transition** — how does dp[i] use smaller states? 4. **Base cases** 5. **Order of computation** (bottom-up) or memo 6. **Complexity**

Word Break vibe `dp[i] = true` if prefix `s[0..i)` can be segmented. Try every end j and dict word.

Red flags Jumping to DP without stating the recurrence. Interviewers will interrupt.

Practice Word Break — write the recurrence on paper first, then code.

Crucible — Interview prep that ends in evidence