Recursion & DP Target: 15s
Before writing any DP code, verify both conditions: overlapping subproblems AND optimal substructure. If only one holds, DP won't help.
RECOGNIZING A DP PROBLEM — CHECKLIST
─────────────────────────────────────
1. OVERLAPPING SUBPROBLEMS?
→ Same function called with same args multiple times
→ Draw the recursion tree: do branches repeat?
2. OPTIMAL SUBSTRUCTURE?
→ Optimal solution built from optimal sub-solutions
→ "Best of X" = best(sub1) + best(sub2)?
3. CLASSIC SIGNALS in problem statement:
□ "minimum cost / maximum profit"
□ "number of ways to..."
□ "can you reach / is it possible"
□ "longest / shortest subsequence"
□ "partition into groups optimally"
4. NOT DP if:
× Need the actual path, not just cost → maybe BFS
× Greedy choice property holds → greedy
× No overlapping subproblems → plain recursionType it from memory. Go.