Fibonacci Number

easy math dp recursion memoization

Problem

F(0) = 0, F(1) = 1, and for n > 1, F(n) = F(n − 1) + F(n − 2). Compute F(n).

Inputn = 7

Output13

Sequence: 0, 1, 1, 2, 3, 5, 8, 13.

def fib(n):
    if n < 2:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

function fib(n) {
  if (n < 2) return n;
  let a = 0, b = 1;
  for (let i = 2; i <= n; i++) {
    const c = a + b;
    a = b;
    b = c;
  }
  return b;
}

class Solution {
    public int fib(int n) {
        if (n < 2) return n;
        int a = 0, b = 1;
        for (int i = 2; i <= n; i++) {
            int c = a + b;
            a = b;
            b = c;
        }
        return b;
    }
}

int fib(int n) {
    if (n < 2) return n;
    int a = 0, b = 1;
    for (int i = 2; i <= n; i++) {
        int c = a + b;
        a = b;
        b = c;
    }
    return b;
}

Explanation

Each Fibonacci number is just the sum of the previous two. The slow way is to call fib(n-1) and fib(n-2) recursively, which re-computes the same values over and over. Instead, this code builds the sequence forward with a simple loop.

We only ever need the last two numbers to make the next one, so we keep just two variables: a holds the value two steps back and b holds the value one step back. We never store the whole list, which is why the space cost is tiny.

The key line is a, b = b, a + b. It slides the window forward: the old b becomes the new a, and a + b becomes the new b (the next Fibonacci number).

Example: for n = 7 we start with a = 0, b = 1. The loop produces 1, 2, 3, 5, 8, 13, and after reaching index 7 the answer in b is 13.

Because we do one pass from 2 up to n and only touch two variables, this runs in O(n) time using O(1) memory.

Time: O(n) Space: O(1)