509_FibonacciNumber - a920604a/leetcode GitHub Wiki

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

class Solution {
public:
    unordered_map<int,int> ans;
    int fib(int n) {
        if(n==0) return 0;
        if(n==1) return 1;
        if(ans.find(n)!=ans.end()) return ans[n];
        ans[n] = fib(n-1) + fib(n-2);
        return ans[n];
    }
};

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

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