Problem link 🔗

(explaination pending)

Code:

C++ (unoptimized, brute-force)

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

C++ (optimized for time)

unordered_map<int,int> memo;
 
class Solution {
public:
    int fib(int n) {
        if (n==0) return 0;
        if (n==1) return 1;
 
        if (memo.count(n)) return memo[n];
 
        int prev1 = fib(n-1);
        int prev2 = fib(n-2);
 
        memo[n-1] = prev1;
        memo[n-2] = prev2;
 
        return prev1+prev2;
    }
};

Big O Analysis

— A

GitHub | Twitter