题解 | #斐波那契数列#

一.题目描述
对于斐波那契数列的介绍：斐波那契数列（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)
优缺点：写法简单，但是没有优化空间了