The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

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

Given n, calculate F(n).

Example 1:

Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Explanation

Fibonacci numbers is a well-known mathematical concept, which we also call the Fibonacci sequence. The Fibonacci sequence is closely related to the golden ratio and this is a great video to explain it:

Recursive Solution

Fibonacci numbers is defined in recursive paradigm, it’s can be implemented easily in a one-line recursive function.

class Solution {
public:
    int fib(int N) {
        return N < 2 ? N : fib(N - 1) + fib(N - 2);
    }
};

The computation process is:

But this algorithm is worst in time complexity:

Time complexity is O(2^N), space complexity is O(N).

Top-bottom Solution with Memoization

To remove the duplicated computation, we can add memoization for the recursive function.

class Solution {
public:
    int fib(int n) { 
        if(n <= 1) return n;
        cache.assign(n+1, 0);
        return memoize(n);
    }

    int memoize(int n) { 
        if(cache[n]) return n;
        cache[n] = fib(n-1) + fib(n-2);
        return cache[n];
    }

    vector<int> cache;
};

Dynamic programming: Iterative Solution

If we use a bottom-top computation style, we could get this iterative solution.

class Solution {
public:
    int fib(int N) {
        if(N == 0) return 0;
        if(N == 1) return 1;
        int l = 0;
        int r = 1;
        while(N--) {
            int t = r;
            r = r + l;
            l = t;
        }
        return l;
    }
};

Preparing for an interview? Check out this!