DP Fundamentals (1D)
Quick reference
| Fibonacci — naive recursive | O(2ⁿ) |
| Fibonacci — memoized (top-down) | O(n) |
| Fibonacci — tabulated, rolling variables | O(n) |
| Climbing Stairs / House Robber — full table | O(n) |
| Climbing Stairs / House Robber — space-optimized | O(n) |
Recursion Basics ended on naive Fibonacci: fib(n) = fib(n-1) + fib(n-2). It is O(2ⁿ), because it computes the exact same subproblem many times. fib(5) calls fib(3) two times. fib(4) calls fib(2) two times. It becomes worse the deeper you go. Dynamic programming is the fix for exactly that symptom, and nothing more: remember the answer to a smaller problem that you already solved, so you never solve it two times. That is the whole idea. Everything else in this phase is that one sentence applied to bigger and bigger problems.
There are two ways to apply it. Memoization is top-down. You keep the recursion exactly as it was, but before any work you check a cache: has this exact input been solved before? If yes, return the stored answer immediately. If no, solve it as normal, then write the answer into the cache before you return, so the next time (yours or someone else's) it is free. Tabulation is bottom-up, with no recursion at all. You build an array of answers from the smallest subproblem (the base case) and fill it in order. Each new entry is built from entries that you already computed. It is the same idea in the opposite direction. Memoization starts at the big problem and works down to the base cases as needed. Tabulation starts at the base cases and works up to the big problem, always.
Think of it as a sticky note. The first time you work out some sub-calculation by hand, you write the answer on a sticky note. The next time you need that exact same sub-calculation, you do not redo the arithmetic. You look at the note. Memoization puts the note on the fridge the moment you first compute something, in case you need it again. Tabulation writes out every note that you are going to need, in order, before you start to use them.
Memoization vs. tabulation, side by side
# Top-down (memoization): keep the recursion, add a cache.
function solve(n, memo = {}):
if n in memo: // seen this exact input before: do not redo the work
return memo[n]
if n is a base case:
return direct answer // base cases do not need caching; they are already O(1)
answer = combine(solve(smaller n, memo), ...)
memo[n] = answer // write the sticky note before you return
return answer
# Bottom-up (tabulation): no recursion. Fill an array from the base case up.
function solve(n):
dp = array of size n + 1
dp[0] = base case answer // seed the base cases BY HAND first
dp[1] = base case answer
for i from 2 to n:
dp[i] = combine(dp[i - 1], dp[i - 2], ...) // build on answers already filled in
return dp[n]Fibonacci, naive — O(2ⁿ), the problem restated
function fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2) // recomputes fib(3), fib(2)... many timesFibonacci, memoized — top-down, O(n)
function fib(n, memo = {}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
return memo[n]Fibonacci, tabulated — bottom-up, O(n) time, O(1) space
function fib(n):
if n <= 1:
return n
prev2 = 0 // fib(0)
prev1 = 1 // fib(1)
for i from 2 to n:
curr = prev1 + prev2
prev2 = prev1
prev1 = curr
return prev1Climbing Stairs — dp[i] = number of ways to reach step i
function climbStairs(n):
if n <= 2:
return n
dp = array of size n + 1
dp[1] = 1 // one way to reach step 1: a single 1-step
dp[2] = 2 // two ways to reach step 2: 1+1, or one 2-step
for i from 3 to n:
dp[i] = dp[i - 1] + dp[i - 2] // the last move was a 1-step, or the last move was a 2-step
return dp[n]House Robber — dp[i] = best haul using houses 0..i
function rob(nums):
if len(nums) == 1:
return nums[0]
dp = array of size len(nums)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i from 2 to len(nums) - 1:
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]) // skip house i, or rob it (and skip i-1)
return dp[len(nums) - 1]The main comparison in this topic is dp[n] in O(n) versus the naive recursive version that it replaces in O(2ⁿ): a jump from exponential to linear, for the cost of a cache. Space for a full 1D table is O(n). When the recurrence looks back only a fixed number of steps (Fibonacci and Climbing Stairs both need only i-1 and i-2), that drops to O(1) with a couple of rolling variables instead of an array.
| Operation | Time | Space | Why |
|---|---|---|---|
| Fibonacci — naive recursive | O(2ⁿ) | O(n) | The calls approximately double at each level down (Recursion Basics). The O(n) is the stack depth, not extra data structures, because no cache exists yet. |
| Fibonacci — memoized (top-down) | O(n) | O(n) | Every fib(k) for k from 0 to n is computed exactly one time and then read from the cache after that: n distinct subproblems, O(1) work each beyond the recursive calls themselves. |
| Fibonacci — tabulated, rolling variables | O(n) | O(1) | The same n subproblems, filled in a loop instead of recursion. And because the recurrence needs only the last two answers, only two variables need to exist at the same time. |
| Climbing Stairs / House Robber — full table | O(n) | O(n) | One dp[i] is computed per index, each in O(1) with already-filled entries. |
| Climbing Stairs / House Robber — space-optimized | O(n) | O(1) | Both recurrences reach back only to i-1 and i-2. The rolling-variable trick from Fibonacci applies unchanged. |
Forgetting to seed the base case(s) by hand
dp[i] = dp[i-1] + dp[i-2] has no meaning until dp[0] and dp[1] (or whatever the smallest indices are) hold real values. Otherwise the recurrence has nothing correct to build on. This is the tabulation twin of the "missing base case" from Recursion Basics. In recursion, a missing base case never terminates. In tabulation, it quietly produces garbage or crashes on an out-of-bounds read, which is often harder to notice.
Inconsistent state definition
Does dp[i] mean "using the first i items" or "the answer at item i itself"? Both are legitimate choices, but the recurrence, the base cases, and the final return value all must agree on which one. To mix them mid-function (for example, an i-1-indexed base case against an i-indexed recurrence) is one of the most common DP bugs. Say the definition out loud in a full sentence before you write any code, the way Build It does for House Robber, and check every line against that sentence.
A memo cache shared across separate calls
A memo dictionary keyed only by n (not by n and whatever else the problem depends on) returns a cached answer that was computed for a completely different array or target: correct-looking output, wrong problem. The usual fix is to pass a fresh cache per top-level call, or to key it by every value that the recurrence actually depends on, not only the loop index.
Space-optimizing before the full version is verified correct
O(1)-space Fibonacci is three lines different from O(n)-space Fibonacci. But to debug which of those three lines is wrong is much harder without an array that you can print and inspect. Get the full-table version correct first. It is easier to reason about and easier to test. Then collapse it to rolling variables once you trust it. To optimize space is the last step, not the first.
Sign in to mark problems done — progress syncs across devices.