Coder's Cat

LeetCode: Fibonacci Number

2020-12-19

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:

fibonacci numbers

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!