Lilly Tech Systems
DP Pattern Recognition
The hardest part of DP is not writing the code — it is recognizing that a problem requires DP and choosing the right pattern. This lesson gives you a decision framework, a pattern matching guide, and answers to the most common DP questions.
Decision Framework: Is This a DP Problem?
When you encounter a problem in a coding exam, run through this checklist in order:
| Step | Question | If Yes | If No |
|---|---|---|---|
| 1 | Does it ask for minimum, maximum, longest, shortest, or count of ways? | Likely DP → continue | Probably not DP |
| 2 | Can you make a choice at each step that affects future steps? | Likely DP → continue | Consider greedy |
| 3 | Does a greedy strategy work? (Can you prove it or find a counterexample?) | Use greedy, not DP | DP is needed → continue |
| 4 | Can you define the state? What parameters uniquely identify a subproblem? | Define state → continue | Rethink the problem |
| 5 | Can you write a recurrence? Does the answer depend on smaller subproblems? | Write recurrence → code it | Maybe divide & conquer |
Pattern Matching Guide
Once you know it is a DP problem, match it to one of these patterns:
| Pattern | Signal Words / Clues | State | Examples |
|---|---|---|---|
| 1D Linear | "at each step", "sequence", "array", single dimension | dp[i] = answer for first i elements | Climbing stairs, house robber, decode ways |
| 2D Grid | "grid", "matrix", "path", "move right/down" | dp[i][j] = answer at cell (i,j) | Unique paths, min path sum |
| Two Sequences | Two strings/arrays, "transform", "common", "distance" | dp[i][j] = answer for first i of seq1, first j of seq2 | Edit distance, LCS, interleaving string |
| Knapsack | "capacity", "weight", "budget", "subset", "partition" | dp[i][w] = answer using items 0..i with capacity w | 0/1 knapsack, subset sum, target sum |
| Interval | "merge", "split", "balloons", "parenthesization", "range" | dp[i][j] = answer for range [i..j] | Burst balloons, MCM, palindrome partition |
| Game Theory | "two players", "optimal play", "turns", "pick from ends" | dp[i][j] = best advantage for current player | Stone game, predict the winner |
| Bitmask | "assign", "visit all", "subset of items", small n (<=20) | dp[mask] or dp[mask][i] | TSP, task assignment, set cover |
| Digit | "count numbers in range [L,R]", "digit property" | dp[pos][sum][tight] | Count numbers with digit sum, digit constraints |
| Tree | "tree structure", "adjacent nodes", "subtree" | dp[node][selected/not] | House robber III, max independent set |
Common Pitfalls
Wrong Base Cases
The most common DP bug. Always verify your base cases with small examples. For counting problems, the empty case usually returns 1 (one way to do nothing), not 0. For optimization, the empty case returns 0 (no cost for nothing).
Wrong Fill Order
In tabulation, you must fill the table so that all dependencies are computed before they are needed. For 1D: left-to-right is usually correct. For 2D: row-by-row top-to-bottom. For intervals: by increasing length. For knapsack 0/1: right-to-left in the capacity dimension.
Off-by-One Errors
DP indices are tricky. Decide early: does dp[i] represent the answer for the first i elements (0-indexed from 1 to n) or the answer ending at index i? Be consistent. Draw the table for a small example to verify.
Missing State Variables
If your memoized solution gives wrong answers, you probably have a state variable missing. Two calls with the same parameters should always return the same result. If they should not (because some external state changed), that external state needs to be part of the key.
Greedy When DP Is Needed
Greedy makes the locally optimal choice. DP considers all choices. If you cannot prove that the greedy choice is globally optimal (exchange argument, matroid, etc.), use DP. Coin change with arbitrary denominations is the classic example where greedy fails.
Stack Overflow in Memoization
Python's default recursion limit is ~1000. For large inputs, memoization hits this limit. Solutions: use sys.setrecursionlimit(), convert to iterative tabulation, or use @lru_cache with care. In contests, always prefer tabulation for large n.
Interview Strategy: The 4-Step Approach
- Identify the pattern (2 minutes): Use the decision framework and pattern matching guide above. State which pattern you see and why.
- Define state and recurrence (3 minutes): Write the state definition and recurrence relation on the board/document before coding. Verify with a small example.
- Code the memoized solution (5-8 minutes): Write brute force recursion, add @lru_cache. This gets you a working solution fast.
- Optimize (5 minutes, if time allows): Convert to tabulation. Apply space optimization. Discuss time and space complexity.
# Interview template (copy this structure for any DP problem)
from functools import lru_cache
def solve(input_data):
# Step 1: Parse input and identify state variables
n = len(input_data)
# Step 2: Memoized recursive solution
@lru_cache(maxsize=None)
def dp(i): # Add more parameters as needed
# Base case
if i == 0: # or i == n, depending on direction
return base_value
# Recurrence: try all choices, take the best
best = initial_value # float('inf') for min, float('-inf') for max
for choice in possible_choices(i):
candidate = dp(smaller_subproblem) + cost_of_choice
best = optimize(best, candidate) # min() or max()
return best
return dp(n) # or dp(0), depending on directionFrequently Asked Questions
How many DP problems should I practice before an interview?
Aim for 30-50 problems across all patterns. Quality matters more than quantity. For each problem, make sure you can write the brute force, memoized, and tabulated solutions from scratch. The 30+ problems in this course cover all major patterns. After completing them, do 10-20 more from LeetCode's "Top Interview Questions" DP section to build speed.
Should I always start with brute force in an interview?
Yes, unless the problem is one you have solved many times and you can directly write the optimized solution confidently. Starting with brute force shows the interviewer your thought process, gives you a working solution to test against, and makes the optimization step clear. Many candidates lose points by jumping to the optimized solution, getting stuck, and having no working code at the end.
How do I handle DP problems I have never seen before?
Follow this exact process: (1) Write the brute force recursive solution. Do not think about DP yet. Just solve the problem recursively by trying all possibilities. (2) Look at the parameters of your recursive function. Those are your DP state variables. (3) Add memoization (cache) on those parameters. You now have a correct DP solution. (4) If needed, convert to tabulation. This process works for ANY DP problem, even ones you have never seen.
When should I use memoization vs tabulation?
Use memoization when: (a) you are in an interview and need a solution fast, (b) not all subproblems need to be solved (sparse state space), or (c) the fill order is complex. Use tabulation when: (a) you need space optimization, (b) n is large and recursion would stack overflow, (c) you are in a contest where speed matters (tabulation avoids function call overhead), or (d) you need to reconstruct the solution path.
How do I know if greedy works instead of DP?
Try to find a counterexample where the greedy choice fails. For coin change with coins [1, 3, 4] and amount 6: greedy picks 4+1+1=3 coins, but optimal is 3+3=2 coins. If you cannot find a counterexample, try to prove the greedy choice property: making the locally optimal choice at each step leads to a globally optimal solution. Activity selection (pick the earliest finishing activity) is provably greedy. If you cannot prove it in 2 minutes, use DP to be safe.
What if my DP solution is too slow?
Check these in order: (1) Is your state too large? Can you remove a dimension? (e.g., sometimes dp[i][j] can be reduced to dp[j] by processing items in order). (2) Is there a mathematical shortcut? (e.g., LIS can go from O(n^2) to O(n log n) with binary search). (3) Can you use bitwise operations? (e.g., subset sum with Python's unlimited integers as bitsets). (4) For competitive programming: convex hull trick, divide and conquer optimization, or Knuth's optimization can reduce certain DP problems by an order of magnitude.
How do I debug a DP solution that gives wrong answers?
Step 1: Test with the smallest possible input and trace through by hand. Step 2: Print the DP table/cache for a small input and verify each cell against your recurrence. Step 3: Compare your DP output against the brute force solution for inputs of size 1-10. Step 4: Check base cases (most common bug). Step 5: Check if your fill order is correct (second most common bug). Step 6: Check for off-by-one errors in indices.
Is DP the same as divide and conquer?
No. Divide and conquer splits a problem into independent subproblems, solves each once, and combines results (merge sort, quicksort). DP is for problems with overlapping subproblems where the same computation would be repeated. If subproblems are independent (no overlap), divide and conquer is sufficient and DP's caching adds no benefit. If subproblems overlap, DP avoids redundant computation through memoization or tabulation.
What are the most frequently asked DP problems in FAANG interviews?
Based on frequency data from interview reports: (1) Coin Change (Amazon, Google), (2) Longest Increasing Subsequence (Google, Meta), (3) Edit Distance (Google, Microsoft), (4) Word Break (Amazon, Meta), (5) House Robber (Amazon), (6) Unique Paths (Microsoft, Amazon), (7) Longest Common Subsequence (Google), (8) 0/1 Knapsack variants (all companies), (9) Decode Ways (Amazon, Meta), (10) Regular Expression Matching (Google, Meta). All of these are covered in this course.
How do I explain DP solutions clearly in an interview?
Use this structure: (1) "The key observation is [overlapping subproblems / optimal substructure property]." (2) "I define dp[i] as [state definition in plain English]." (3) "The recurrence is dp[i] = [formula], because [reasoning]." (4) "The base cases are [list them]." (5) Write the code. (6) "The time complexity is O(...) because [reason]. Space is O(...) and can be optimized to O(...) because [reason]." This structure shows clear thinking and is what interviewers want to hear.
Course Summary
You have completed the Dynamic Programming Patterns course. Here is what you learned:
| Lesson | Problems | Key Pattern |
|---|---|---|
| 1. DP Fundamentals | Fibonacci, Climbing Stairs | Overlapping subproblems, memoization vs tabulation |
| 2. 1D DP | 6 problems | Include/exclude, linear scan with state |
| 3. 2D DP | 5 problems | Grid paths, two-sequence alignment, interval splits |
| 4. Knapsack | 5 problems | Include/exclude with capacity, subset sum reduction |
| 5. String DP | 5 problems | Character matching, segmentation, pattern matching |
| 6. Interval & Game | 5 problems | Range splits, last-operation trick, minimax |
| 7. Optimization | 6 examples | Space reduction, bitmask subsets, digit counting, tree DP |
| 8. Pattern Recognition | Decision framework | Identify, match pattern, code, optimize |