Learning Outcome
Design DP state, transition, base case, and answer extraction before writing code.
Pattern Recognition
| Item | Detail |
|---|---|
| Core signal | The problem asks for best/count/possible over choices and brute force repeats the same subproblems. |
| Use when | You can describe the remaining problem with a small state tuple. |
| Avoid when | The required invariant is not monotonic or the input constraints point to a simpler direct scan. |
Intuition
DP is cached recursion: first define what the function means, then optimize storage later.
Exact Practice Question Names
- Climbing Stairs
- Coin Change
- Coin Change II
- Word Break
- Unique Paths
- Dungeon Game
- Partition Equal Subset Sum
- Longest Increasing Subsequence
Interview Approach
- Write the recursive meaning of dp state.
- Identify choices and transition.
- Set base cases for impossible and complete states.
- Memoize, then convert to tabulation if useful.
- Compress space only after correctness is clear.
Pseudocode
dp[state] = answer for this remaining subproblem
for each valid choice from state:
candidate = combine(choice, dp[next_state])
dp[state] = best/count/or of candidates
return dp[start_state]Sample Dry Run
In coin change, dp[amount] is the fewest coins for that amount. dp[11] checks 1 + dp[10], 1 + dp[9], and 1 + dp[6] for coins [1,2,5].
Edge Cases
- Impossible states
- Zero amount
- Order matters vs does not matter
- Subsequence vs subarray
Common Mistakes
- Coding a table before defining state
- Double counting combinations as permutations
- Compressing space in the wrong loop order
Complexity
| Item | Detail |
|---|---|
| Expected time | Depends on states times transitions; commonly O(n*target), O(mn), or O(n log n) for optimized LIS. |
| Expected space | Number of states, sometimes compressible. |
Java, C++ and Python Notes
- Java: prefer explicit classes and clear helper methods over clever one-liners.
- C++: use vector, unordered_map, set, priority_queue, and long long when sums can grow.
- Python: keep state readable with dict, set, deque, heapq, and lru_cache where appropriate.
Quick Revision Checklist
- Name the pattern before coding.
- State the invariant or DP state in one sentence.
- Dry-run the smallest non-trivial example.
- Close with time and space complexity.