Recursion - Easy Level - Question 2

Recursion - Easy Level - Question 2

Question 2

Leetcode 509 Fibonacci Number

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).

Constraints:

0 <= n <= 30

Analysis:

1. the base case is obvious: F(0) and F(1);

2. the converging formula is given directly as well;

So just need to convert them into code.

See the code below:

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

But if you have learned some algorithm before and had some understanding of time and space complexity, you can immediately realize that the above method is NOT the most efficient one. The reason is that we re-calculated so many inter-mediates many times! For example, fib(N-2) was calculated when calculating fib(N-1), which was calculated again when calculating fib(N-2) itself. 

We just can use a trick called dynamic programming, to memorize the calculated states, and just reuse them when called again.

See the code below:

class Solution {
public:
    int fib(int N) {
        if(N<2) return N;
        vector<int> dp(N+1, 0);
        dp[1] = 1;
        for(int i=2; i<=N; ++i) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[N];
    }
};

Since we just need the last two elements, so the space complexity can be further reduced.

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

Upper Layer