【牛客题霸题解】斐波那契数列

题面描述

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。
n<=39

斐波哪契数列

一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔都不死，那么一年以后有多少对兔子？
我们可以把这些兔子的数量以对为单位列出数字就能得到一组数字：1、1、2、3、5、8、13、21、34、55、89、144、233。所以，过了一年之后，总共会有233对兔子了。那么续往下呢？
其实这组数字可以形成一个有规律的数列，这个数列的规律是这样的：它的第一项、第二项是1,而从第三项起每一项都等于它的前两项之和。这个数列是在1228年意大利数学家斐波那契首先提出的。我们把这个数列叫做“斐波那契数列”。在这个数列中的数字，就被称为“斐波那契数”。

设f(n)表示斐波那契数列中的第n个数，则

$\begin{cases} f(1)=1\\ f(2)=1\\ f(n)=f(n-1)+f(n-2) \end{cases}$

那么就可以很容易的写出递归代码,因为题目中说明请你输出斐波那契数列的第n项（从0开始，第0项为0）。

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

因为f(0)=0,f(1)=1,f(2)=f(0)+f(1),所以也可以把代码合并一下

class Solution {
public:
    int Fibonacci(int n) {
        if(n&lt;2)//小于2的时候f(n) = n
        {
            return n;
        }
        else{
            return Fibonacci(n-1)+Fibonacci(n-2);
        }
    }
};

但是提交发现合并后的代码超时，因合并后的代码多计算了一层，f(2) = f(0)+f(1),而原来的代码是直接返回的。多计算的这一层有这么大的影响么？
我们来观察这个递归的时间复杂度
以n=6为例做递归决策树
图片说明

我们不难发现在这棵树中有很多结点是重复的，而且重复的结点数会随着n的增加而急剧增加，这意味计算量会随着n的增加而急剧增大。
可以发现复杂度肯定是指数级的。
具体复杂度的计算
证明网址：https://www.geeksforgeeks.org/time-complexity-recursive-fibonacci-program/
结果为 $O（1.6180^n）$
现在就遇到了一个问题，怎么样才能避免重复计算呢？
我们建立一个数组，把算出的答案存到数组里，使用的时候直接取就可以了。

class Solution {
public:
    int dp[10000];
    int Fibonacci(int n) {
        if(dp[n])
        {
            return dp[n];
        }
        if(n&lt;2)//小于2的时候f(n) = n
        {
            return n;
        }
        else if(n==2){
           return 1;
        }
        else{
            return dp[n]=Fibonacci(n-1)+Fibonacci(n-2);
        }
    }
};

优化以后的递归决策树如下

这种思路其实就是记忆化搜索算法

记忆化搜索简介

记忆化搜索实际上是递归来实现的，但是递归的过程中有许多的结果是被反复计算的，这样会大大降低算法的执行效率。
而记忆化搜索是在递归的过程中，将已经计算出来的结果保存起来，当之后的计算用到的时候直接取出结果，避免重复运算，因此极大的提高了算法的效率。

继续对这个问题进行思考，我们知道 $f(1)$ 和 $f(2)$ 以后，可以推出 $f(3)$ ,然后可以推出 $f(4)$ ,之后可以推出 $f(5)$ ....所以我们直接算到n，就可以得出答案了

class Solution {
public:
    int Fibonacci(int n) {
        int dp[10000];
        dp[1] = dp[2] = 1;
        for(int i = 3 ; i &lt;= n ;i++)
        {
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
};

继续对这个问题进行思考，我们知道 $𝑓(1)$ 和 $𝑓(2)$ 以后，可以推出 $𝑓(3)$ 然后可以推出 $𝑓(4)$ 之后可以推出 $𝑓(5)$ ....所以我们一直推算到 $𝑛$ ，就可以得出答案了
C++版本代码：

class Solution {
public:
    int Fibonacci(int n) {
        if(n==0){return 0;}
        if(n==1||n==2){return 1;}
        int f1,f2,ans;
        f1=f2=ans=1;//f1,f2分别表示f(n-1)和f(n-2)
        for(int i = 3 ; i <= n ;i++)//从f(3)递推到f(n)
        {
            ans = f1+f2;
            f1 = f2;
            f2 = ans;
        }
        return ans;
    }
};

python版本代码：

class Solution:
    def Fibonacci(self, n):
        if n==0:
            return 0
        if n==1 or n==2:
            return 1
        f1 = f2 = ans = 1
        i = 3
        while(i<=n):
            ans = f1+f2
            f1 = f2
            f2 = ans
            i+=1
        return ans

扩展：
对于本题的数据范围：𝑛 ≤39 ，时间复杂度𝑂(𝑛)的算法已经足够了。

但是如果我把题目进行一下扩展：
数据范围 𝑛≤10^18，求𝐹𝑖𝑏𝑜𝑛𝑎𝑐𝑐𝑖(𝑛) % 1000000009 的结果

因为n的范围很大，求出的斐波那契数也会很大，为了避免大数计算，出题时一般会让求解答案%某个素数的结果
取模运算满足以下性质，所以在计算的过程中可以先取模在进行运算，来保证数据一直处于非溢出的范围内
(a + b) % p = (a%p + b%p) %p
(a – b) % p = ((a%p – b%p) + p) %p
(a * b) % p = (a%p)*(b%p) %p。

对于扩展后的题目，我们可以用矩阵快速幂优化递推

时间复杂度可以达到𝑂(log⁡𝑛)

图片说明
所以只需要求

所求结果

现在我们来思考一下，如何快速的计算一个数/矩阵的n次幂：
如何快速地计算 $𝑎^𝑛$ ?
如果正常计算，是把𝑛个𝑎相乘，时间复杂度𝑂(𝑛)

我们来观察一下，以求𝑎的10次方为例： $𝑎^10= 𝑎^{(1010)_2}=𝑎^{1×2^3+0×2^2+1×2^1+0×2^0 }= 𝑎^{1×2^3 }×𝑎^{1×2^1 }$
这样来看的话，我们的答案是从 $𝑎^{2^𝑘}$ 中的某些相乘得出的，而 $𝑎^{2^𝑘 }$
可以直接从上一项相乘得出
图片说明
这样的话，计算𝑛次幂的复杂度从𝑂(𝑛)变成了𝑂(𝑙𝑜𝑔𝑛)
如何快速地计算 $𝑎^𝑛$ ?-代码

int quick_pow(int a, int n)
{
    int res=1;
    while (n > 0)
    {
        if (n & 1){res = res * a;}
        a = a * a;
        n >>= 1;
    }
    return res;
}

斐波那契数列矩阵快速幂解法代码

#include <iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int MOD = 1000000009;
struct Matrix
{
    ll m [2][2];
    Matrix(bool unit = false)
    {
        memset(m, 0, sizeof(m));
        if (unit){m [0][0] = m[1][1] =1;}
    }
    Matrix operator*(const Matrix& other) const
    {
        Matrix res;
        for (int i = 0; i < 2; ++i){
            for (int j = 0; j < 2; ++j){
                for (int k = 0; k < 2; ++k){
                  res.m[i][j] += m[i][k] * other.m[k][j];
                  res.m[i][j] %= MOD;
                }
            }
        }
        return res;
    }
};
Matrix quick_pow(Matrix a, ll n)
{
    Matrix res(true);
    while (n > 0)
    {
        if (n & 1){res = res * a;}
        a = a * a;
        n >>= 1;
    }
    return res;
}
int main()
{
    ll n;
    cin >> n;
    Matrix mat;
    mat.m[0][1] = mat.m[1][0] = mat.m[1][1] = 1;
    mat.m[0][0] = 0;
    mat = quick_pow(mat, n - 1);
    ll ans = mat.m[0][0] + mat.m[0][1];
    ans %= MOD;
    cout<<ans<<endl;
    return 0;
}