Fibonacci DP
O(n) SpaceO(1) Imagine computing your family tree by hand. To find your great-great-grandparent count, you’d keep re-counting the same branches. Instead, write down each generation’s count as you go — each new answer builds on the previous two. That’s DP: solve small problems first, reuse their answers.
When to use it: The Fibonacci pattern appears whenever the answer for step n depends on the answers for steps n-1 and n-2: climbing stairs (1 or 2 steps), tiling problems, counting paths, or any linear recurrence.
Key insight: Naive recursion solves the same subproblems exponentially many times (O(2^n)). Storing each result and reusing it reduces this to O(n) — the essence of dynamic programming.
Common trap: Using O(n) space when only the last two values are needed. For Fibonacci-style recurrences, two variables suffice — no need for a full array.
# Top-down (memoization)
memo = {}
function fibMemo(n):
if n <= 1: return n
if n in memo: return memo[n]
memo[n] = fibMemo(n - 1) + fibMemo(n - 2)
return memo[n]
# Bottom-up (tabulation)
function fibTable(n):
if n <= 1: return n
dp = array of size n + 1
dp[0] = 0
dp[1] = 1
for i = 2 to n:
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
# Space-optimized (only need last two values)
function fibOptimal(n):
if n <= 1: return n
prev2 = 0
prev1 = 1
for i = 2 to n:
current = prev1 + prev2
prev2 = prev1
prev1 = current
return prev1from functools import lru_cache
def fib_memo(n: int) -> int:
"""Top-down with memoization."""
@lru_cache(maxsize=None)
def helper(k: int) -> int:
if k <= 1:
return k
return helper(k - 1) + helper(k - 2)
return helper(n)
def fib_tabulation(n: int) -> int:
"""Bottom-up with tabulation."""
if n <= 1:
return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
def fib_optimal(n: int) -> int:
"""Space-optimized: O(1) space."""
if n <= 1:
return n
prev2, prev1 = 0, 1
for _ in range(2, n + 1):
prev2, prev1 = prev1, prev1 + prev2
return prev1
def climb_stairs(n: int) -> int:
"""Number of ways to climb n stairs taking 1 or 2 steps at a time."""
if n <= 2:
return n
prev2, prev1 = 1, 2
for _ in range(3, n + 1):
prev2, prev1 = prev1, prev1 + prev2
return prev1
def min_cost_climbing_stairs(cost: list[int]) -> int:
"""Minimum cost to reach the top, starting from step 0 or 1."""
n = len(cost)
prev2, prev1 = cost[0], cost[1]
for i in range(2, n):
prev2, prev1 = prev1, cost[i] + min(prev1, prev2)
return min(prev1, prev2)Problem: You are climbing a staircase with n steps. Each time you can climb 1 or 2 steps. How many distinct ways can you reach the top?
How would you approach this?
Answer: This is the Fibonacci DP pattern. The number of ways to reach step n is the sum of ways to reach step n-1 (then take 1 step) and step n-2 (then take 2 steps). Base cases: 1 way for step 1, 2 ways for step 2.
Problem: Given an array cost where cost[i] is the cost to step on stair i, find the minimum cost to reach the top. You can start from step 0 or 1 and take 1 or 2 steps at a time.
How would you approach this?
Answer: This is Fibonacci-style DP with a min instead of sum. dp[i] = cost[i] + min(dp[i-1], dp[i-2]). Optimize to O(1) space since you only need the last two values.
Time: O(n) because each subproblem (from 0 to n) is computed exactly once, and each takes O(1) work. This is a dramatic improvement over naive recursion's O(2^n).
Space: O(1) for the optimized version that only keeps the last two values. The tabulation version uses O(n) for the dp array. The memoized version uses O(n) for the cache plus O(n) call stack.