Fibonacci with Dynamic Programming

Almost every dynamic programming course starts with Fibonacci. There is a good reason for that. The plain version looks simple. But it hides a problem that makes your code painfully slow. Once you see the problem, the dynamic programming fix makes a lot of sense. So let us start with the slow code. We will watch it struggle. Then we will fix it step by step.

🧮 What Is the Fibonacci Series?

The Fibonacci series is a list of numbers. Each number is the sum of the two before it. The first two numbers are 0 and 1. After that, you just keep adding.

So the series goes like this:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

See the pattern? 0 plus 1 is 1. Then 1 plus 1 is 2. Then 1 plus 2 is 3. And it keeps going.

In math we write it as a recurrence. That just means a rule that defines a value using earlier values:

fib(0) = 0
fib(1) = 1
fib(n) = fib(n - 1) + fib(n - 2)

Our job is simple. Given a number n, find fib(n).

🐌 The Slow Way: Plain Recursion

The recurrence above almost writes the code for itself. If n is 0 or 1, return n. Otherwise return fib(n - 1) + fib(n - 2). That is it.

Here is that idea in Python:

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

This is correct. It gives the right answer. But it is shockingly slow for larger n. Why? Let us look at what it actually computes.

Say we ask for fib(5). To get that, it needs fib(4) and fib(3). To get fib(4), it needs fib(3) and fib(2). Notice fib(3) already showed up twice. And it only gets worse deeper down.

Here is the call tree:

Look at fib(3). We compute it once on the left and again on the right. The same work, done twice. For bigger n the same small problems get solved again and again, thousands of times. We call these repeated problems overlapping subproblems. That means the big problem keeps breaking into the same smaller problems.

💡 The DP Idea: Remember What You Already Solved

Dynamic programming is one simple idea. If you are going to solve the same small problem again and again, solve it once and save the answer. Next time you need it, just read the saved answer instead of computing it again.

There are two common ways to do this.

• Memoization (top-down): keep the recursion, but store each answer in a table the first time you compute it. Before computing fib(k), check the table. If it is already there, return it.
• Tabulation (bottom-up): drop the recursion. Start from the smallest values and fill an array from fib(0) upward until you reach fib(n).

Let us see the bottom-up version, because it is the cleanest. We make an array dp where dp[i] holds fib(i). We set dp[0] = 0 and dp[1] = 1. Then we walk forward and fill each spot using the two spots before it.

def fib(n):
    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]

Now each value is computed exactly once. That brings the time down from O(2^n) to a clean O(n). That is a huge difference.

✂️ One More Step: Save Only the Last Two Values

The tabulation version is fast. But look closely at the loop. To compute dp[i], we only ever use dp[i - 1] and dp[i - 2]. We never look further back. So why keep the whole array in memory?

We do not need to. We can keep just two variables for the last two values, and one more to hold the new sum. This is the space-optimized version. That means we cut down the extra memory we use.

Here is how it works in points:

• Keep prev2 for fib(i - 2) and prev1 for fib(i - 1). Start them at 0 and 1.
• In each step, the next value is prev1 + prev2.
• Then slide the window forward. prev2 becomes the old prev1. And prev1 becomes the new value.
• After the loop, prev1 holds the answer.

This keeps the O(n) speed but uses only O(1) extra space. That is the best version. So let us write it in all five languages.

🛠️ Steps to Compute Fibonacci (Space-Optimized)

Before the code, here is the full plan in order.

1. Handle the small cases first. If n is 0 or 1, just return n.
2. Set prev2 = 0 (this is fib(0)) and prev1 = 1 (this is fib(1)).
3. Loop i from 2 up to n.
4. Compute current = prev1 + prev2.
5. Slide the window. Set prev2 = prev1, then prev1 = current.
6. When the loop ends, prev1 is fib(n). Return it.

💻 Code in 5 Languages

We compute fib(10), which should be 55. We also print the first 11 values so you can see the series build up.

#include <stdio.h>

// Space-optimized Fibonacci: O(n) time, O(1) extra space
long long fib(int n) {
    if (n <= 1) return n;        // small cases
    long long prev2 = 0;         // fib(0)
    long long prev1 = 1;         // fib(1)
    long long current = 0;
    for (int i = 2; i <= n; i++) {
        current = prev1 + prev2; // next value
        prev2 = prev1;           // slide the window
        prev1 = current;
    }
    return prev1;                // fib(n)
}

int main(void) {
    printf("First 11 Fibonacci numbers: ");
    for (int i = 0; i <= 10; i++) {
        printf("%lld ", fib(i));
    }
    printf("\n");
    printf("fib(10) = %lld\n", fib(10));
    return 0;
}

First 11 Fibonacci numbers: 0 1 1 2 3 5 8 13 21 34 55
fib(10) = 55

#include <iostream>
using namespace std;

// Space-optimized Fibonacci: O(n) time, O(1) extra space
long long fib(int n) {
    if (n <= 1) return n;        // small cases
    long long prev2 = 0;         // fib(0)
    long long prev1 = 1;         // fib(1)
    long long current = 0;
    for (int i = 2; i <= n; i++) {
        current = prev1 + prev2; // next value
        prev2 = prev1;           // slide the window
        prev1 = current;
    }
    return prev1;                // fib(n)
}

int main() {
    cout << "First 11 Fibonacci numbers: ";
    for (int i = 0; i <= 10; i++) {
        cout << fib(i) << " ";
    }
    cout << endl;
    cout << "fib(10) = " << fib(10) << endl;
    return 0;
}

First 11 Fibonacci numbers: 0 1 1 2 3 5 8 13 21 34 55
fib(10) = 55

public class Fibonacci {

    // Space-optimized Fibonacci: O(n) time, O(1) extra space
    static long fib(int n) {
        if (n <= 1) return n;        // small cases
        long prev2 = 0;              // fib(0)
        long prev1 = 1;              // fib(1)
        long current = 0;
        for (int i = 2; i <= n; i++) {
            current = prev1 + prev2; // next value
            prev2 = prev1;           // slide the window
            prev1 = current;
        }
        return prev1;                // fib(n)
    }

    public static void main(String[] args) {
        System.out.print("First 11 Fibonacci numbers: ");
        for (int i = 0; i <= 10; i++) {
            System.out.print(fib(i) + " ");
        }
        System.out.println();
        System.out.println("fib(10) = " + fib(10));
    }
}

First 11 Fibonacci numbers: 0 1 1 2 3 5 8 13 21 34 55
fib(10) = 55

# Space-optimized Fibonacci: O(n) time, O(1) extra space
def fib(n):
    if n <= 1:
        return n              # small cases
    prev2 = 0                 # fib(0)
    prev1 = 1                 # fib(1)
    for i in range(2, n + 1):
        current = prev1 + prev2  # next value
        prev2 = prev1            # slide the window
        prev1 = current
    return prev1              # fib(n)


print("First 11 Fibonacci numbers:", " ".join(str(fib(i)) for i in range(11)))
print("fib(10) =", fib(10))

First 11 Fibonacci numbers: 0 1 1 2 3 5 8 13 21 34 55
fib(10) = 55

// Space-optimized Fibonacci: O(n) time, O(1) extra space
function fib(n) {
  if (n <= 1) return n;        // small cases
  let prev2 = 0;               // fib(0)
  let prev1 = 1;               // fib(1)
  let current = 0;
  for (let i = 2; i <= n; i++) {
    current = prev1 + prev2;   // next value
    prev2 = prev1;             // slide the window
    prev1 = current;
  }
  return prev1;                // fib(n)
}

const series = [];
for (let i = 0; i <= 10; i++) {
  series.push(fib(i));
}
console.log("First 11 Fibonacci numbers:", series.join(" "));
console.log("fib(10) =", fib(10));

First 11 Fibonacci numbers: 0 1 1 2 3 5 8 13 21 34 55
fib(10) = 55

📊 Comparing the Three Approaches

Here is how the three versions stack up. Same problem, very different cost.

⚠️ Common Mistakes to Avoid

A few small slips trip people up here. Keep an eye out for these.

• Forgetting the small cases. If you do not return early for n = 0 and n = 1, your loop math breaks.
• Sliding the window in the wrong order. You must save prev1 into prev2 and then put the new value into prev1. Swap that order and you lose a value.
• Starting the loop at the wrong place. The first two values are already known. So the loop begins at i = 2, not at 0 or 1.
• Sticking with plain recursion in an interview. It works for tiny n. But it shows you missed the overlapping subproblems. Always reach for the DP version.

🧩 What You’ve Learned

• ✅ The Fibonacci series adds the two previous numbers, with fib(0) = 0 and fib(1) = 1.
• ✅ Plain recursion is correct but runs in O(2^n) time because it solves the same subproblems again and again.
• ✅ Dynamic programming fixes this by solving each subproblem once and saving the answer.
• ✅ Memoization is top-down, tabulation is bottom-up, and both run in O(n) time.
• ✅ The space-optimized version keeps only the last two values, giving O(n) time and O(1) extra space.

🚀 What’s Next?

• Memoization vs Tabulation
• Climbing Stairs