题解 | #斐波那契数列#

方法一：递归

斐波那契数列：f(n) = f(n-1) + f(n+1) （n>2）。可以将问题分解，使用递归解答。

时间复杂度：o(2ⁿ)。

空间复杂度：o(n)。递归栈深度

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

方法二：递归

上述递归会有很多重复的计算，可以利用一个数组将数列保存下来，这样可以避免递归过程的重复计算。

时间复杂度：o(n)。

空间复杂度：o(n)。递归栈深度

class Solution {
  public:
    int fn[50] = {0};
    int Fibonacci(int n) {
        if (n == 1 || n == 2)
            return 1;
        if (fn[n] > 0)
            return fn[n];

        fn[n] = Fibonacci(n - 1) + Fibonacci(n - 2);
        return fn[n];
    }
};  

方法三：动态规划

直接从最小的序列开始计算，直到得到想要序列。

时间复杂度：o(n)。

空间复杂度：o(1)。

class Solution {
  public:
    int Fibonacci(int n) {
        if (n == 1 || n == 2)
            return 1;

        int temp1 = 1;
        int temp2 = 1;
        int res;
        for (int i = 2; i < n; i++) {
            res = temp1 + temp2;
            temp1 = temp2;
            temp2 = res;
        }
        return res;
    }
};