Synthesis: which pattern to use?
Five DP patterns covered — and this is the last section of the course. Let's wrap up with the DP decision tree and then a look back at everything you built.
The DP decision tree
Recognize the DP: are there subproblems that REPEAT and does the answer build from the smaller ones?
1. How to model the state?
├── a position in a sequence → dp[i] (1D DP)
├── a target value to compose with items → dp[a] (knapsack)
├── a cell in a grid → dp[r][c] (grid DP)
└── prefixes of TWO sequences → dp[i][j] (string DP)
2. What is the recurrence (how does dp build from the smaller states)?
├── sum/count paths → dp[i-1] + dp[i-2] / sum
├── decide include or exclude → max(exclude, include)
├── minimize with reusable items → min(dp[a-item] + 1)
└── compare last elements → match? diagonal : neighbors
3. Base cases and fill order (from the smaller ones to the bigger).
And the section's reflexes: time ≈ states × cost per state; when the recurrence looks only at the last k states, reduce the space; and, before reaching for DP, ask whether a greedy already solves it.
The complete map of the section
| Pattern | State | Time |
|---|---|---|
| 1D DP | dp[i] (position) | O(n) |
| Include/exclude | dp[i] = max(skip, take) | O(n) |
| Knapsack | dp[a] (target value) | O(target × items) |
| Grid DP | dp[r][c] (cell) | O(m·n) |
| Sequence DP | dp[i][j] (prefixes) | O(m·n) |
The mother idea: DP is recursion + memory. Define the state, the recurrence, and the base cases, and the rest is filling a table. What seemed like the most frightening topic is, deep down, the most systematic method of the course.
Section quiz
Statements you haven't seen in the lessons. Identify the pattern and the why. 6+ correct: ready for the course's final exam.
🧠 Section quiz: Dynamic Programming
0/61. 'Minimum cost to climb a staircase, where each step charges a cost (steps of 1 or 2).' Which pattern?
2. 'Split an array into two subsets with equal sum.' Which pattern?
3. 'Edit distance: the minimum of insertions/removals/substitutions to transform one string into another.' Which pattern?
4. 'Longest increasing subsequence in an array.' 1D or 2D, and why?
5. 'In how many ways can you decode a string of digits into letters (A=1..Z=26)?' Which pattern?
6. What is the fastest way to estimate the time complexity of a DP?
You finished the course 🎉
If you made it this far, you covered every type of problem in the Top 75:
- Fundamentals (Big-O) and the Array and String patterns — the base.
- Binary, Linked List, Matrix, Intervals — structures and techniques.
- Trees, Heap, Graphs — recursion and advanced structures.
- Dynamic Programming — where everything comes together.
And more important than the problems: you trained the way of thinking — solving by hand, finding the waste in brute force, recognizing the pattern, and justifying the complexity. Notice how the patterns talk to each other: the Array hash map reappears in String and Graphs; DFS/BFS runs through Matrix, Tree, and Graph; Kadane was already DP. They weren't 75 isolated problems — they were about 20 reused patterns.
The final exam
This section's exam has three brand-new problems — Min Cost Climbing Stairs (easy), Partition Equal Subset Sum (medium), and Edit Distance (hard) — with hidden cases. After it, the best next step is to open LeetCode and solve problems without a net: now you have the map.
Good luck on the exam — and congratulations on completing the course! Go back to the section page and click "Final exam".