sol_020.md

Fibonacci Number - Practice - LeetCode

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.

Example:2

Input: 
n = 3

Output: 
2

Explanation: 
F(3) = F(2) + F(1) = 1 + 1 = 2.

Example:3

Input: 
n = 4

Output: 
3

Explanation: 
F(4) = F(3) + F(2) = 2 + 1 = 3.

Solution 1 : Recursion

Time - O(2^N)
Space - O(N)

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

Solution 2 : Memoization

Time - O(N)
Space - O(N) + O(N)

class Solution {
public:
	int fib_memoization(int n, vector<int> &dp){
		if (n < 2) return n;
		if (dp[n] != -1) return dp[n];
		return dp[n] = fib_memoization(n-1, dp) + fib_memoization(n-2, dp);
	}

    int fib(int n) {
    	vector<int> dp(n+1, -1);
		return fib_memoization(n, dp);
    }
};

Solution 3 : Dynamic Programming

Time - O(N)
Space - O(N)

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

Solution 4 : Space Optimization

Time - O(N)
Space - O(1)

class Solution {
public:
    int fib(int n) {
		int prev1 = 0;
		int prev2 = 1;
		int curr = 0;
		for (int i = 1; i <= n; i++){
			curr = prev1 + prev2;
			prev2 = prev1;
			prev1 = curr;
		}
		return curr;
    }
};