On this page
Description
Some problems have answers built from answers to smaller versions of themselves. The ways to climb n stairs are the ways to climb n - 1 plus the ways to climb n - 2. Written as plain recursion, the same smaller answers get recomputed an enormous number of times. Naive fib(30) makes 2,692,537 calls to compute 31 distinct values. Dynamic programming (DP) computes each distinct subproblem once and reuses it. This skill covers the one-dimensional case: a state, a recurrence, base cases, and a table filled in order.
We'll go from simple to more technical:
- The pattern: define dp[i], write the recurrence, seed the base cases, fill in order.
- A second flavor: a choice at every step (House Robber), where greedy fails.
- Where DP shows up in production (pricing, parsing, planning).
- What breaks it: no caching, wrong base cases, sentinels that overflow, and recursion depth.
The approach
Three decisions, in this order:
- State - what
dp[i]means, in words. ("dp[i] = number of ways to reach step i.") - Recurrence - how
dp[i]follows from smaller states. ("dp[i] = dp[i - 1] + dp[i - 2].") - Base cases - the smallest states, answered directly. ("dp[0] = 1, dp[1] = 1.")
Java
int climbStairs(int n) {
int prev2 = 1, prev1 = 1; // dp[0] and dp[1]
for (int i = 2; i <= n; i++) {
int curr = prev1 + prev2; // dp[i] = dp[i - 1] + dp[i - 2]
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
Python
def climb_stairs(n: int) -> int:
prev2, prev1 = 1, 1 # dp[0] and dp[1]
for i in range(2, n + 1):
prev2, prev1 = prev1, prev1 + prev2 # dp[i] = dp[i - 1] + dp[i - 2]
return prev1
This is tabulation: fill answers from the base cases upward, in an order where everything dp[i] reads is already computed. Because the recurrence reads only the last two values, two variables replace the whole table - O(1) space. The alternative, memoization, keeps the natural recursion and caches each result the first time it's computed; it produces the same answers and only visits states that are actually reachable (coin change with coins {5, 10} and amount 1,000 touches 200 states, not 1,001), at the cost of recursion depth.
A second flavor: a choice at every step
Often the recurrence isn't a sum but a choice. House Robber - take values from an array, never two adjacent, maximize the total - asks at each house: skip it, or take it on top of the best total two houses back.
Java
int rob(int[] nums) {
int twoBack = 0, oneBack = 0; // best totals up to i - 2 and i - 1
for (int x : nums) {
int best = Math.max(oneBack, twoBack + x); // skip house i, or take it
twoBack = oneBack;
oneBack = best;
}
return oneBack;
}
Python
def rob(nums: list[int]) -> int:
two_back, one_back = 0, 0 # best totals up to i - 2 and i - 1
for x in nums:
best = max(one_back, two_back + x) # skip house i, or take it
two_back, one_back = one_back, best
return one_back
Greedy shortcuts fail on this kind of problem. Taking every other house misses [2, 1, 1, 2] (the answer 4 uses the first and last), and "always take the largest coin" misses coins {1, 3, 4} for 6 (3 + 3 beats 4 + 1 + 1). When a local choice can block a better global answer, DP compares the choices instead of committing to one.
Where you'll see it
Text layout engines break paragraphs into lines with DP (TeX's line breaking minimizes total "badness" over all break points), diff tools align files with DP, speech and handwriting recognizers decode with the Viterbi algorithm (DP over time steps), and resource planners compute cheapest schedules by DP over days or budget. In each, the state is small, the recurrence is local, and the answers are reused many times.
Which tool for which job?
| You need | Use |
|---|---|
| Overlapping subproblems with a 1D state | a table filled from the base cases up |
| Only the last few values matter | rolling variables, O(1) space |
| Few states actually reachable | top-down memoization |
| A huge n with a linear recurrence | matrix exponentiation or fast doubling, O(log n) |
| How the answer was reached | keep the full table and trace back |
| A local choice that can block a better answer | DP, not greedy |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
| Recursion without caching | naive fib(30) makes 2,692,537 calls | memoize or tabulate |
| Wrong base cases | every later value is wrong | check the smallest inputs by hand |
Integer.MAX_VALUE as "impossible" | + 1 wraps negative and wins every min | amount + 1, or check before adding |
long counts that grow like Fibonacci | climbing stairs wraps at n = 92 | BigInteger, or the modulus the problem gives |
| Deep top-down recursion | stack overflow / RecursionError | bottom-up |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. Why does naive recursive Fibonacci take exponential time, and what fixes it?
Show answer
fib(n) calls fib(n - 1) and fib(n - 2), which call overlapping subproblems again and again - fib(30) makes 2,692,537 calls for 31 distinct values. Caching each value (memoization) or computing them bottom-up (tabulation) solves each subproblem once: O(n).
2. Coin change fills dp with Integer.MAX_VALUE for "impossible" and computes dp[i - c] + 1. What goes wrong?
Show answer
Integer.MAX_VALUE + 1 wraps to Integer.MIN_VALUE, a huge negative number that wins every min. For coins {2} and amount 3, the answer comes out as -2,147,483,648 instead of -1. Use a sentinel like amount + 1 (more coins than could ever be needed) or skip impossible states before adding.
3. When can a DP keep two variables instead of an array?
Show answer
When each state reads only the previous one or two states, and you only need the final value. If you also need to reconstruct the choices (which houses were robbed), keep the full table or parent pointers - rolling variables forget how each value was reached.
Key takeaways
- DP = state + recurrence + base cases; get the state's meaning written down first.
- Each distinct subproblem is solved once - exponential recursion becomes polynomial.
- Memoization (top-down, only reachable states, uses the stack) and tabulation (bottom-up, no recursion limit) give the same answers.
- Keep only what the recurrence reads - O(1) space when it looks back a fixed distance.
- Choose sentinels for "impossible" that can't overflow, and watch the answer's own size.