Recognizing DP problems

We've reached the last and most feared section. But here's a secret: you've already done DP in this course. Kadane (Array) and recursion on trees were dynamic programming in disguise. DP is just recursion that doesn't repeat work.

As always, each pattern lesson opens with a 🎯 Try it first.

What dynamic programming is

DP solves a problem by breaking it into smaller subproblems and reusing the answers to those subproblems instead of recomputing them. Two conditions must be present:

1. Overlapping subproblems: the same subproblem shows up many times.
2. Optimal substructure: the problem's answer is built from the answers to the subproblems.

The canonical example is Fibonacci. The naive recursion recomputes the same values an exponential number of times:

                 fib(5)
            /              \
        fib(4)            fib(3)
       /     \           /     \
   fib(3)   fib(2)   fib(2)   fib(1)     ← fib(3) and fib(2) recomputed!

Run it and see the waste — the naive version makes thousands of calls; the one with memoization (remembering what it already computed) makes a few dozen:

Memoization vs tabulation: the two flavors of DP

There are two ways to do DP, and they give the same answer:

Most lessons will use tabulation (the dp table), because it makes the recurrence explicit and visible — and you get to watch the table fill in.

The method for solving any DP

Faced with a DP problem, answer three questions:

1. What is the state? What does dp[i] (or dp[i][j]) mean? (e.g., "the maximum using the first i elements".)
2. What is the recurrence? How is dp[i] built from smaller states? (e.g., dp[i] = max(dp[i-1], ...).)
3. What are the base cases? The initial values that don't depend on anyone.

With these three defined, the code almost writes itself.

Big-O in DP: states × cost per state

Here is the section's Big-O deep dive, and the most useful shortcut for estimating the complexity of a DP:

Time ≈ (number of states) × (cost to compute each state).

• 1D DP with an O(1) recurrence: n states × O(1) = O(n).
• 2D DP (two strings of sizes m and n): m·n states × O(1) = O(m·n).
• Coin change: amount states × O(coins) per state = O(amount · coins).

And the space is the size of the table — often you can reduce it (if dp[i] only depends on dp[i-1], you keep two variables instead of the whole array, dropping to O(1)). That's why memoization trades exponential time for polynomial: it limits the work to the number of distinct states.

The section's problems

• Climbing Stairs, House Robber → 1D DP, include/exclude
• Coin Change, Combination Sum IV → knapsack
• Unique Paths → grid DP
• Longest Common Subsequence, LIS, Word Break, Decode Ways → DP on sequences/strings

Summary

• DP = recursion without repeating work; needs overlapping subproblems + optimal substructure.
• Memoization (recursion + cache) and tabulation (loop filling dp) give the same result.
• Method: define the state, recurrence, and base cases.
• Time ≈ states × cost per state; space is the table (often reducible).

Next lesson: the simplest recurrence of all — 1D DP.