🧠 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

ChapterTopicThe Big IdeaLevel
Chapter 6.1Introduction to DPMemoization, tabulation, the four-step DP recipeBronze/Silver
Chapter 6.2Classic DP ProblemsLIS, knapsack, grid paths, counting waysSilver
Chapter 6.3Advanced DP PatternsBitmask DP, interval DP, tree DPSilver/Gold
Chapter 6.4Meet in the MiddleTurn 2^N into two 2^(N/2) searches and mergeGold
Chapter 6.5Digit DPFill 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 to 10^18, solved using digit DP
    • Combined states: digit sum, remainder, previous digit, occurrence count, and upper-bound constraints

Key DP Patterns to Master

PatternChapterExample ProblemKey Reminder
1D DP (sequential)6.1Fibonacci, climbing stairsDefine the state before writing the recurrence
1D DP (optimization)6.1Coin change, minimum coinsInitialize minimum values with INF
1D DP (counting)6.1Coin change, number of waysCounting base case is often dp[0]=1
2D DP6.20/1 knapsack, grid pathsExplain what each dimension means
LIS6.2O(N²) and O(N log N) LISThe tails array is not necessarily an actual LIS
Bitmask DP6.3TSP, assignment problemmask represents a set
Interval DP6.3Matrix chain multiplication, merging stonesFill by increasing interval length
Tree DP6.3Independent set on treesCompute children before the parent
Meet in the Middle6.4Subset sum, max subset sum ≤ X2^40 is impossible, but two 2^20 lists are fine
Digit DP6.5Avoiding a digit, digit sum, divisibilitytight 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, and upper_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:

  1. What is the state? What information describes a subproblem?
  2. What is the transition? Which smaller or simpler states can produce this one?
  3. What are the base cases? Which states are known without computation?
  4. 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

  1. Do not skip Chapter 6.1. You need to understand states and transitions, not just memorize code.
  2. Write classic problems twice. Try both memoized recursion and bottom-up tabulation.
  3. Focus on knapsack and LIS in Chapter 6.2. They appear as substructures in many harder problems.
  4. Chapter 6.3 enters Silver/Gold territory. Bitmask, interval, and tree DP require stronger state design.
  5. Chapter 6.4 is not traditional DP, but it is just as important. When you see N≤40 and subset enumeration, think meet in the middle.
  6. Draw states for Chapter 6.5. Digit DP's tight, started, and pos are much easier to understand with a small hand trace.
  7. Check boundaries in every DP. Empty sets, zero, negative values, L=0, array dimensions, and INF overflow are all common traps.

⚠️ Warning: The #1 DP bug: forgetting to check dp[w-c] != INF before using it in a minimization DP. INF + 1 can 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 tight or started usually fails on boundary cases.