(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