Recursion & DP Target: 15s
Defining the state is the hardest part of DP. Get this right and the recurrence writes itself.
DP STATE DEFINITION — "WHAT CHANGES?"
──────────────────────────────────────
Ask: what variables change between subproblems?
COMMON STATE PATTERNS:
1D: dp[i] = answer for first i items
→ climbing stairs, house robber, word break
2D: dp[i][j] = answer for items i..j (intervals)
→ palindrome, matrix chain, burst balloons
OR dp[i][j] = answer using i items with capacity j
→ knapsack, edit distance, LCS
State machine: dp[i][state]
→ stock buy/sell (hold/sold/rest)
→ house robber circular
Bitmask: dp[mask] = answer for subset represented by mask
→ TSP, partition to K subsets
CHECKLIST:
□ What is the "answer" stored in dp[...]?
□ What are the dimensions? (index, capacity, state)
□ What are the transitions? dp[i] = f(dp[i-1], ...)
□ What are the base cases?Type it from memory. Go.