🧠 Part 6: Dynamic Programming
The most powerful and most trainable topic in competitive programming. Master memoization, tabulation, classic DP models, meet-in-the-middle, and digit DP on your path from USACO Silver to Gold.
📚 5 Chapters · ⏱️ Estimated 4-6 weeks · 🎯 Target: USACO Silver → Gold
Part 6: Dynamic Programming
Estimated time: 4-6 weeks
Dynamic programming is not about memorizing formulas. It is about breaking one large problem into many repeated subproblems, defining the right state, designing the transition, handling boundaries, and knowing when DP is not the best tool. This part starts from basic 1D DP and gradually moves into knapsack, LIS, bitmask DP, interval DP, tree DP, meet in the middle, and digit DP.
What Topics Are Covered
| Chapter | Topic | The Big Idea | Level |
|---|---|---|---|
| Chapter 6.1 | Introduction to DP | Memoization, tabulation, the four-step DP recipe | Bronze/Silver |
| Chapter 6.2 | Classic DP Problems | LIS, knapsack, grid paths, counting ways | Silver |
| Chapter 6.3 | Advanced DP Patterns | Bitmask DP, interval DP, tree DP | Silver/Gold |
| Chapter 6.4 | Meet in the Middle | Turn 2^N into two 2^(N/2) searches and merge | Gold |
| Chapter 6.5 | Digit DP | Fill digits from left to right to count numbers in [L, R] | Gold |
What You'll Be Able to Solve After This Part
After completing Part 6, you'll be ready to tackle:
-
USACO Bronze:
- Simple counting problems: how many ways can we do something?
- Basic optimization problems: minimum cost or maximum profit
-
USACO Silver:
- Longest increasing subsequence and its variants
- 0/1 knapsack, unbounded knapsack, and two-dimensional knapsack
- Grid path counting and maximum-value paths
- 1D/2D DP with careful state definitions
-
USACO Gold:
- Bitmask DP, interval DP, and tree DP
- Exponential subset problems with
N≈40, solved using meet in the middle - Counting digit-property numbers in
[L, R]up to10^18, solved using digit DP - Combined states: digit sum, remainder, previous digit, occurrence count, and upper-bound constraints
Key DP Patterns to Master
| Pattern | Chapter | Example Problem | Key Reminder |
|---|---|---|---|
| 1D DP (sequential) | 6.1 | Fibonacci, climbing stairs | Define the state before writing the recurrence |
| 1D DP (optimization) | 6.1 | Coin change, minimum coins | Initialize minimum values with INF |
| 1D DP (counting) | 6.1 | Coin change, number of ways | Counting base case is often dp[0]=1 |
| 2D DP | 6.2 | 0/1 knapsack, grid paths | Explain what each dimension means |
| LIS | 6.2 | O(N²) and O(N log N) LIS | The tails array is not necessarily an actual LIS |
| Bitmask DP | 6.3 | TSP, assignment problem | mask represents a set |
| Interval DP | 6.3 | Matrix chain multiplication, merging stones | Fill by increasing interval length |
| Tree DP | 6.3 | Independent set on trees | Compute children before the parent |
| Meet in the Middle | 6.4 | Subset sum, max subset sum ≤ X | 2^40 is impossible, but two 2^20 lists are fine |
| Digit DP | 6.5 | Avoiding a digit, digit sum, divisibility | tight and started are the core flags |
Prerequisites
Before starting Part 6, make sure you can:
- Write recursive functions and understand the call stack (Chapter 2.3)
- Use arrays, 2D vectors, and simple structs comfortably (Chapter 2.3)
-
Understand sorting, binary search,
lower_bound, andupper_bound(Chapter 3.3) - Understand bit operations and bitmask enumeration (Chapter 2.6)
- Solve basic DFS/BFS problems (Chapter 5.2) — DP and graph search both explore state spaces
The DP Mindset
DP is not about memorizing formulas. It is about asking four questions repeatedly:
- What is the state? What information describes a subproblem?
- What is the transition? Which smaller or simpler states can produce this one?
- What are the base cases? Which states are known without computation?
- What is the evaluation order? Dependencies must be computed before they are used.
💡 Key Insight: If brute force recomputes the same subproblem many times, DP caches it. If brute force is too large but can be split into two independent halves, meet in the middle may be more natural than DP. If the numeric range is too large to enumerate but the constraints depend only on digits, digit DP is often the answer.
Tips for This Part
- Do not skip Chapter 6.1. You need to understand states and transitions, not just memorize code.
- Write classic problems twice. Try both memoized recursion and bottom-up tabulation.
- Focus on knapsack and LIS in Chapter 6.2. They appear as substructures in many harder problems.
- Chapter 6.3 enters Silver/Gold territory. Bitmask, interval, and tree DP require stronger state design.
- Chapter 6.4 is not traditional DP, but it is just as important. When you see
N≤40and subset enumeration, think meet in the middle. - Draw states for Chapter 6.5. Digit DP's
tight,started, andposare much easier to understand with a small hand trace. - Check boundaries in every DP. Empty sets, zero, negative values,
L=0, array dimensions, andINFoverflow are all common traps.
⚠️ Warning: The #1 DP bug: forgetting to check
dp[w-c] != INFbefore using it in a minimization DP.INF + 1can overflow!The #2 DP bug: wrong loop order for 0/1 knapsack vs. unbounded knapsack. Backward iteration means each item is used at most once; forward iteration allows unlimited use.
The #1 Gold DP bug: missing a state dimension. In digit DP, omitting
tightorstartedusually fails on boundary cases.