思路:

  • 斐波那契数列公式为: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的动态数组