Chapter 10: Problem Recognition Drills
You have learned the patterns, derived recurrences, and even optimized beyond O(n²). But there is one skill that separates people who know DP from people who can use DP under pressure: recognizing which pattern fits before writing a single line of code.
This skill is not innate — it is built through deliberate practice. Read a problem statement, classify the pattern, define the subproblem, and check your answer. The drills below are designed for exactly that. Do not rush. Wrong guesses are learning opportunities, not failures.
Pattern recognition is the meta-skill of dynamic programming. Once you can glance at a problem and think “this is interval DP on a range,” the five-step framework from Chapter 2 does the rest. These drills train that glance.
Quick Reference: All Patterns
Keep this table in mind as you work through the drills. The “key signal” column is what you should look for in the problem statement.
| Pattern | Key Signal | Subproblem Shape | Example |
|---|---|---|---|
| 1D DP | Linear sequence, decision at each index | dp[i] | House Robber |
| 2D DP | Two sequences, or grid | dp[i][j] | LCS, Knapsack |
| Interval | Splitting/merging ranges | dp[i][j] for range [i,j] | Matrix Chain |
| Tree | DP on tree structure | dp[node] | House Robber III |
| Bitmask | Subset tracking, n ≤ 20 | dp[mask] | TSP |
| Digit | Count numbers with digit properties | dp[pos][state][tight] | Count Special |
Drill Set 1: Pattern Classification
Read each problem statement and select the DP pattern it belongs to. After answering, read the explanation — even for problems you got right — to reinforce the signals that led to the correct classification.
Given an array, find the maximum sum of non-adjacent elements.
Drill Set 2: Subproblem Definition
Recognizing the pattern is step one. Step two is defining what your DP table represents. A vague definition like “dp[i] is the answer for i” is not enough — be precise about what is included, excluded, and optimized.
Rod Cutting: What does dp[i] represent?
Palindrome Partitioning: What does dp[i] represent?
Egg Drop: What does dp[k][n] represent?
Longest Palindromic Subsequence: What does dp[i][j] represent?
Word Break: What does dp[i] represent?
If you cannot write a one-sentence definition of dp[i] or dp[i][j], you are not ready to write the recurrence. Pause, re-read the problem, and ask: “What is the smallest subproblem whose answer I need to know?”
Spaced Repetition Review
The problems below combine everything from Drill Set 1 with ten additional problems for variety. The spaced repetition system tracks which problems you find easy and surfaces the ones you need to review. Come back to this section over the next few days — spaced practice is how recognition becomes automatic.
Spaced Repetition Review
Problems you miss come back sooner. Correct answers space out over time.
20 due for review
0 scheduled for later
Closing Remarks
Congratulations — you have worked through the full arc of dynamic programming: from mindset and the five-step framework, through every major pattern, to advanced optimizations and now deliberate recognition practice. That is a serious body of knowledge.
But mastery is not a destination. Keep practicing with the 5-step framework every time you encounter a new problem:
- Define the subproblem precisely.
- Identify the last decision.
- Write the recurrence.
- Establish base cases.
- Determine fill order.
For more problems, explore the Dynamic Programming tag on LeetCode. Start with medium problems in patterns you know, then branch into unfamiliar territory and classify before you code.
The best competitive programmers and engineers do not memorize solutions — they recognize shapes. Every problem in this tutorial was an instance of a pattern you now know. The next problem you face will be too. Trust the process, keep drilling, and the glance will get faster every week.