Fibonacci Number: Bottom-Up Dynamic Programming

May 20, 20264 min read

leetcodeproblemeasydynamic-programming

You are given an integer n. Return the nth Fibonacci number, where F(0) = 0, F(1) = 1, and F(n) = F(n-1) + F(n-2) for n > 1.

This is LeetCode 509: Fibonacci Number, and it is the purest possible introduction to dynamic programming. No story about stairs or robbers or coins. Just the raw recurrence, waiting for you to implement it efficiently. If you have never built a DP solution from scratch, start here.

The problem

Given n, compute F(n) where the Fibonacci sequence is defined as:

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) for all n >= 2

For example, F(5) = 5 because the sequence goes 0, 1, 1, 2, 3, 5.

Each Fibonacci value is the sum of the two before it. F(i) = F(i-1) + F(i-2).

The approach

The naive recursive approach calls fib(n-1) and fib(n-2) at every level, creating an exponential blowup of duplicate work. For n = 30, the recursive version makes over a billion calls.

The fix is bottom-up dynamic programming. Instead of starting at n and recursing down, you start at F(0) and build forward. Each value depends only on the two values right before it, so you can compute the entire sequence in a single pass with O(n) time.

Because each Fibonacci value depends on only the two previous values, you do not even need an array. Two variables are enough, bringing space down to O(1).

Step-by-step walkthrough

Let's compute F(5) using bottom-up DP. At each step, the yellow cells are the sources being added, and the green cell is the value being computed.

Base cases: F(0) = 0, F(1) = 1

The first two Fibonacci values are defined directly. F(0) = 0 and F(1) = 1.

F(2) = F(1) + F(0) = 1 + 0 = 1

Add the two previous values. 1 + 0 = 1.

F(3) = F(2) + F(1) = 1 + 1 = 2

Slide the window forward. 1 + 1 = 2.

F(4) = F(3) + F(2) = 2 + 1 = 3

Same pattern. 2 + 1 = 3.

F(5) = F(4) + F(3) = 3 + 2 = 5

Final result: F(5) = 5.

A few things to notice:

The window of "active" cells slides forward by one position at each step.
You never look further back than two positions, which is why two variables can replace the entire array.
The base cases F(0) = 0 and F(1) = 1 anchor the entire computation. Without them, there is nothing to build from.

Drill DP problems with SRS

The code

def fib(n):
    if n < 2:
        return n

    prev2 = 0
    prev1 = 1

    for i in range(2, n + 1):
        current = prev1 + prev2
        prev2 = prev1
        prev1 = current

    return prev1

if n < 2: return n handles both base cases in one line, since F(0) = 0 and F(1) = 1.

prev2 and prev1 track the two most recent Fibonacci values. They start as F(0) = 0 and F(1) = 1.

The loop iterates from i = 2 to i = n. At each step, current is the sum of the two previous values. Then the window slides: prev2 becomes prev1, and prev1 becomes current.

After the loop, prev1 holds F(n).

Complexity analysis

Approach	Time	Space
Bottom-up DP	O(n)	O(1)

Time: O(n). You compute each Fibonacci value from F(2) to F(n) exactly once. Each computation is a single addition, so the total work is linear.

Space: O(1). You only store two variables (prev2 and prev1) regardless of how large n is. No array, no recursion stack, no memo dictionary.

Practice this problem with spaced repetition

Building blocks

This problem is built on linear DP with constant state. You iterate through a sequence, and at each position you compute a value that depends on a fixed number of previous values. Because the lookback window is constant, you replace the full DP array with a handful of variables.

Building block 1: Two-variable sliding window

prev2 = base_0
prev1 = base_1

for i in range(2, n + 1):
    current = prev1 + prev2
    prev2 = prev1
    prev1 = current

This template works for any recurrence of the form dp[i] = f(dp[i-1], dp[i-2]). Swap out the combination function for different problems: addition for Fibonacci and Climbing Stairs, max for House Robber.

Building block 2: Base-case guard

if n < 2:
    return n

When a DP recurrence needs at least two prior values, always guard the base cases before entering the loop. This prevents index errors and keeps the loop body clean. The same guard appears in Climbing Stairs (if n <= 1: return 1) and House Robber (if len(nums) <= 1).

Edge cases

n = 0: return 0. The zeroth Fibonacci number is 0 by definition.
n = 1: return 1. Only one value in the sequence so far.
n = 2: return 1. The first "computed" value, F(2) = F(1) + F(0) = 1 + 0 = 1.
Large n (up to 30): the O(1) space solution handles the LeetCode constraint instantly. No risk of stack overflow since there is no recursion.

A common mistake is writing the base case as if n == 0: return 0 and then letting the loop start at i = 1. This breaks because prev2 would reference a value before F(0), which does not exist. Always initialize both prev2 = F(0) and prev1 = F(1) before the loop starts at i = 2.

From understanding to recall

The Fibonacci recurrence is simple enough that you might think you will never forget it. But the real skill is not remembering F(n) = F(n-1) + F(n-2). It is recognizing the two-variable sliding window pattern and applying it automatically when you see a new DP problem. That pattern is the building block behind Climbing Stairs, House Robber, Decode Ways, and many others.

Spaced repetition turns recognition into reflex. You revisit the constant-state linear DP template at increasing intervals, write it from scratch each time, and after a few reps the pattern is automatic. No more fumbling with base cases or forgetting which variable gets updated first.

Climbing Stairs - Same recurrence with a different story wrapped around it, the natural next step after Fibonacci
House Robber - Same two-variable DP skeleton, but with a max decision at each step
Decode Ways - Another two-variable lookback problem, this time counting valid string decodings

Start drilling DP patterns today