一.题目描述
对于斐波那契数列的介绍:斐波那契数列(Fibonacci sequence),又称黄金分割数列,因数学家莱昂纳多·斐波那契(Leonardoda Fibonacci)以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:0、1、1、2、3、5、8、13、21、34、……在数学上,斐波那契数列以如下被以递推的方法定义:F(0)=0,F(1)=1, F(n)=F(n - 1)+F(n - 2)(n ≥ 2,n ∈ N*)(来源百度)

现在要求一个斐波那契数列((从0开始,第0项为0,第1项是1))的第n项是多少?

二.算法1(递归解法)
从斐波那契数列的计算公式:图片说明 ,可自然想到该问题适合使用递归法求解,下面直接给代码。
图片说明

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

复杂度:o(2^n)
优缺点:写法简单,但是指数级的复杂度太高,在所求位数较大时响应时长无法接受。
三.算法2(循环数组)
如果说前面的递归解法是自顶向下将大问题拆解成小问题求解,那么循环解法则是逆向思维,自底向上,先求出小问题的解,再向上一步一步向上求取最终问题的解。求解过程分为n步,将每一步的结果保存在列表中对应下标的位置,代码如下。
图片说明

class Solution {
public:
    int Fibonacci(int n) {
           int dp[45];
           dp[1]=1;
           dp[2]=1;
           for(int i=3;i<=n;i++){//这块需要注意 是从第3项开始的
               dp[i]=dp[i-1]+dp[i-2];
           }
           return dp[n];
    }
};

复杂度:单层循环,时间复杂度为o(n)
优缺点:写法简单,但是没有优化空间了