The Concept
The concept
What DP Actually Is (The Unfearful Version)
Dynamic programming is not a new algorithm — it's an optimization of recursion. When you write a recursive solution to a problem and notice that the same subproblem is computed multiple times, you cache the result. That's it. DP = recursion + caching.
The classic example: Fibonacci. Naive recursion computes fib(5) by computing fib(3) twice, fib(2) three times, fib(1) five times. The recursion tree has exponential redundant work. Add a cache (memoization) and each subproblem is computed once — O(n) instead of O(2^n).
The two conditions that make DP applicable:
- Overlapping subproblems: the recursion recomputes the same state multiple times. If each subproblem is unique, caching doesn't help and DP is useless.
- Optimal substructure: the optimal answer to the big problem can be built from optimal answers to smaller subproblems. If the big problem's answer depends on non-optimal sub-answers, DP can't construct the optimum.
Once you identify these two properties, the solution follows a mechanical process: define what dp[i] means, write the recurrence that relates dp[i] to smaller states, set base cases, and choose an evaluation order (top-down with memoization or bottom-up with a table). The hard part is step 1 — defining the state. Once the state is right, the recurrence usually falls out naturally.
The framework
Two conditions that tell you DP is the right tool:
You're solving the "climbing stairs" problem: how many distinct ways can you climb n stairs if you take 1 or 2 steps at a time? Define the DP state and recurrence before coding.
dp[i] = "number of distinct ways to reach step i." To reach step i, your last move was either 1 step (from i-1) or 2 steps (from i-2). So dp[i] = dp[i-1] + dp[i-2]. Base cases: dp[0]=1 (one way to be at the ground), dp[1]=1 (one way to take 1 step). This is Fibonacci in disguise — the classic DP warmup.
1. Overlapping subproblems : the recursion tree recomputes the same state multiple times
2. Optimal substructure : the optimal answer to the big problem uses optimal sub-answers
Three steps to any DP problem:
1. Define the subproblem : dp[i] means "___" (fill this in before any code)
2. Write the recurrence : dp[i] = f(dp[j], dp[k], ...)
3. Define base cases : the smallest inputs with known answers
Write these on paper (or say them aloud in an interview) before touching code.