1. 暴力解法

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

2. dp 数组的迭代解法

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

3. 带备忘录的递归解法

class Solution {
public:
    int fib(int n) {
        if(n == 0) return 0;
        vector<int> memory(n+1, 0);
        return helper(memory, n);
    }

    int helper(vector<int>& memory, int n) {
        if(n == 1 || n == 2) return 1;
        if(memory[n] != 0) return memory[n];
        memory[n] = helper(memory, n-1) + helper(memory, n-2);
        return memory[n];
    }
};

4. 状态压缩 dp

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