题解 | #斐波那契数列#

class Solution {
public:
    int f[50] = {0};
    int Fibonacci(int n) {
        if (n <= 2) return 1;
        if (f[n] > 0) return f[n];   //递归 + 记忆化搜索，时间O(n)，只算了f[1到n],没有重复计算，空间复杂度O(n),栈深度为n
        return f[n] = (Fibonacci(n-1)+Fibonacci(n-2));
    }
};
/*class Solution {
public:
    int Fibonacci(int n) {
        if (n<=2) return 1;
        return Fibonacci(n-1) + Fibonacci(n-2);
    }
//递归法：时间复杂度：O(2^n) 空间复杂度O(n);
};*/
/*
    int Fibonacci(int n) {
        // write code here
        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[n];
    }
};
//动态规划：时间复杂度：O(n) 空间复杂度：O(n) 
*/
/*
int Fibonacci(int n) {
        if (n == 1 || n == 2){
            return 1;
        }
        // write code here
        int a = 1;  //状态压缩
        int b = 1;
        int tmp;
        for (int i = 3; i <= n; i++){
            tmp = a + b;
            a = b;
            b = tmp;
        }
        return tmp;
    }
//动态规划 + 状态压缩：时间复杂度：O（n） 空间复杂度：O（1）
*/