BM62. [斐波那契数列]

https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295

BM62. 斐波那契数列

https://www.nowcoder.com/practice/c6c7742f5ba7442aada113136ddea0c3?tpId=295&sfm=discuss&channel=nowcoder

思路：

• 斐波那契数列公式为:F(n)=F(n-1)+F(n-2)
• 可以直接从i=0与i=1开始，直接相加得到i=2的值，然后将i=1与i=2相加，依次类推，直到i=n,一个循环可以解决
• 也可以用递归方法解决，将上述公式看作函数，不断调用相加即可，递归更简洁

方法一：直接相加法
具体做法：
设置一个a=0，b=1，依次相加并更新a与b，直到第n个。

class Solution {
public:
    int Fibonacci(int n) {
        if (n <= 1)    //从0开始，第0项是0，第一项是1
             return n;
         int res = 0;
         int a = 0;
         int b = 1;
         for (int i=2; i<=n; i++){//因n=2时也为1，初始化的时候把a=0，b=1
         //第三项开始是前两项的和,然后保留最新的两项，更新数据相加
             res = (a + b);
             a = b;
             b = res;
         }
        return res;
    }
};

复杂度分析：

• 时间复杂度：O(n)，其中n为输入的数
• 空间复杂度：O(1)，未申请空间

方法二：递归法

class Solution {
public:
    int Fibonacci(int n) {
        if (n <= 1)    //从0开始，第0项是0，第一项是1
             return n;
        else{
            return Fibonacci(n - 1) + Fibonacci(n - 2); //根据公式递归调用函数
        }
        return 0;
    }
};

复杂度分析：

• 时间复杂度：O(2^n)，每个递归会调用两个递归，因此呈现2的指数增长
• 空间复杂度：O(n), 递归栈的最大深度

方法三：动态数组法
具体做法：创建一个n+1大小的动态数组temp，初始化第0位为0，第1位为1，然后根据公式相加即可得到后面的，数组最后的下标n即为所求。

class Solution {
public:
    int Fibonacci(int n) {
        if (n <= 1)    //从0开始，第0项是0，第一项是1
             return n;
        int* temp = new int[n+1];
        temp[0] = 0;
        temp[1] = 1;
        for (int i = 2; i <= n; i++)
        {
            temp[i] = temp[i-1] + temp[i-2];
        }
        return temp[n];
    }
};

复杂度分析：

• 时间复杂度：O(n)，一个for循环遍历
• 空间复杂度：O(n)，创建了一个大小为n+1的动态数组