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), and it's O(2ⁿ) because it recomputes the exact same subproblem over and over — fib(5) calls fib(3) twice, fib(4) calls fib(2) twice, and it only gets worse the deeper you go. Dynamic programming is the fix for exactly that symptom, and nothing more: remember the answer to a smaller problem you've already solved, so you never solve it twice. That's 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 doing any work you check a cache — has this exact input been solved before? If yes, hand back the stored answer instantly. If no, solve it like normal, then write the answer into the cache before returning, so the next time (yours or someone else's) it's free. Tabulation is bottom-up: no recursion at all. You build an array of answers starting from the smallest subproblem — the base case — and fill it in order, each new entry built from entries you already computed. Same idea, opposite direction: memoization starts at the big problem and works down to base cases as needed; tabulation starts at the base cases and works up to the big problem, always.
Think of it like a sticky note. The first time you work out some sub-calculation by hand, you jot the answer on a sticky note. Next time you need that exact same sub-calculation, you don't redo the arithmetic — you glance at the note. Memoization is sticking the note on the fridge the moment you first compute something, in case you need it again. Tabulation is writing out every note you're going to need, in order, before you start using 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 — don't redo the work
return memo[n]
if n is a base case:
return direct answer // base cases don't need caching, they're already O(1)
answer = combine(solve(smaller n, memo), ...)
memo[n] = answer // write the sticky note before returning
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 case(s) 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 times overFibonacci, 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] // last move was a 1-step, or 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 headline comparison in this topic is dp[n] in O(n) versus the naive recursive version 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 only looks back a fixed number of steps (Fibonacci, Climbing Stairs — both only need 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) | Calls roughly double each level down (Recursion Basics); the O(n) is stack depth, not extra data structures — no cache exists yet. |
| Fibonacci — memoized (top-down) | O(n) | O(n) | Every fib(k) for k from 0 to n is computed exactly once and then read from cache forever after — n distinct subproblems, O(1) work each beyond the recursive calls themselves. |
| Fibonacci — tabulated, rolling variables | O(n) | O(1) | Same n subproblems, filled in a loop instead of recursion — and since the recurrence only ever needs the last two answers, only two variables need to exist at once. |
| Climbing Stairs / House Robber — full table | O(n) | O(n) | One dp[i] computed per index, each in O(1) using already-filled entries. |
| Climbing Stairs / House Robber — space-optimized | O(n) | O(1) | Both recurrences only reach back 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] is meaningless until dp[0] and dp[1] (or whatever the smallest indices are) hold real values — the recurrence has nothing correct to build on otherwise. This is the tabulation twin of Recursion Basics' "missing base case": in recursion a missing base case never terminates, in tabulation it just 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 have to agree on which one — mixing them mid-function (using an i-1-indexed base case against an i-indexed recurrence, for instance) is one of the most common DP bugs there is. Say the definition out loud in a full sentence before writing 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) will happily return a cached answer computed for a completely different array or target — correct-looking output, wrong problem. The usual fix is passing a fresh cache per top-level call, or keying it by every value the recurrence actually depends on, not just 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 debugging which of those three lines is wrong is much harder without an array you can print and inspect. Get the full-table version correct first — it's easier to reason about and easier to test — then collapse it to rolling variables once you trust it. Optimizing space is the last step, not the first.
Sign in to mark problems done — progress syncs across devices.