Part 6: Dynamic Programming

Estimated time: 3–4 weeks

Dynamic programming is the most powerful and most feared topic in competitive programming. Once you master it, you'll be able to solve problems that seem impossible by brute force. Take your time with this part — it's worth it.

What Topics Are Covered

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 to do X?)
  • Basic optimization (minimum cost to do Y?)

• USACO Silver:

  • Longest increasing subsequence (and variants)
  • Knapsack-style resource allocation
  • Grid path problems (max value path, count paths)
  • 1D DP with careful state definition (Hoof-Paper-Scissors, etc.)

• DP on intervals or trees (Chapter 6.3)

Key DP Patterns to Master

Prerequisites

Before starting Part 6, make sure you can:

• Write recursive functions and understand the call stack (Chapter 2.3)
• Use 2D vectors comfortably (Chapter 2.3)
• Understand binary search (Chapter 3.3) — needed for O(N log N) LIS
• Solve basic BFS problems (Chapter 5.2) — DP and BFS share "state space exploration" intuition

The DP Mindset

DP is not about memorizing formulas — it's about asking the right questions:

1. What is the "state"? What information do I need to describe a subproblem?
2. What is the "transition"? How does the answer to a bigger state depend on smaller states?
3. What are the base cases? What are the simplest subproblems with known answers?
4. What order do I fill the table? Dependencies must be computed before they're used.

💡 Key Insight: If you find yourself writing the same computation multiple times in a recursive solution, DP is the fix. Cache the result the first time, reuse it every subsequent time.

Tips for This Part

1. Start with Chapter 6.1 carefully. Don't rush to knapsack before you truly understand Fibonacci DP. The "why" of DP is more important than the "what."
2. Write both memoization and tabulation for the same problem. Converting between them deepens understanding.
3. Chapter 6.2's LIS has two implementations: O(N²) (easy to understand) and O(N log N) (fast, needed for large N). Learn both.
4. Chapter 6.3 is Silver/Gold level. If you're targeting Bronze, you can skip Chapter 6.3 initially and return to it later.
5. Most DP bugs come from wrong initialization. For min-cost problems, initialize to INF, not 0. For counting problems, initialize the base case to 1, not 0.

⚠️ Warning: The #1 DP bug: forgetting to check dp[w-c] != INF before using it in a minimization DP. INF + 1 overflows!

The #2 DP bug: wrong loop order for 0/1 knapsack vs. unbounded knapsack. Backward iteration = each item used at most once. Forward iteration = unlimited use.