题解 | #斐波那契数列#

斐波那契数列：最直观的想法是，由于fib(x)=fib(x-1)+fib(x-2)，其中x>=3，当x=1或者2时，fib(x)=1，那么我们不妨令a=1，b=1，c=1，其中循环从3开始直到n，不断交替变换，使得c=a+b，a=b，b=c，如此最后c即是我们想要的结果。

int Fibonacci(int n) {
        int a=1,b=1,c=1;
        for(int i=3;i<=n;i++)
        {
            c=a+b;
            a=b;
            b=c;
        }
        return c;
    }

idea：由于题目直接给出了递推公式，那么我们也可以使用递归来做。

int Fibonacci(int n) {
        int f;
        if((n==1)||(n==2))
            return 1;
        if(n>=3)
            f=Fibonacci(n-1)+Fibonacci(n-2);
        return f;
    }

idea：既然有递推公式，也可以使用递归来做，那么必然可以使用动态规划来做，因为递归是将大问题分解为小问题，而动态规划是将小问题推导为大问题。

int Fibonacci(int n) {
        vector<int> dp(n);
        dp[0]=1;
        dp[1]=1;
        for(int i=2;i<n;i++)
            dp[i]=dp[i-1]+dp[i-2];
        return dp[n-1];
    }

数学：由于有fib(n)=fib(n-1)+fib(n-2)，然后又有fib(n-1)=fib(n-2)+fib(n-3)……，该题本质上是求fib(n)对应计算了多少次的fib(1)和多少次的fib(0)，那么我们可以转换为如下公式，最后结果为矩阵的n-1次方的第一行第一列的数。

typedef struct Matrix{
    int a,b,c,d; //2*2矩阵
}Matrix;

Matrix Matrix_Multiply(Matrix &x,Matrix &y) //矩阵乘法
{
    Matrix z;
    z.a=x.a*y.a+x.b*y.c;
    z.b=x.a*y.b+x.b*y.d;
    z.c=x.c*y.a+x.d*y.c;
    z.d=x.c*y.b+x.d*y.d;
    return z;
}

Matrix Matrix_Quick_Pow(Matrix &x,int n) //矩阵快速幂
{
    Matrix ans={1,0,0,1}; //初始化为单位矩阵
    while(n>0)
    {
        if(n&1) //最低位为1
            ans=Matrix_Multiply(ans, x); //将x乘入结果
        x=Matrix_Multiply(x, x); //将x乘以x为下次做准备
        n>>=1; //右移一位
    }
    return ans;
}

class Solution {
public:
    int Fibonacci(int n) {
        //最后结果为矩阵的n-1次方的第一行第一列的数
        Matrix x={1,1,1,0}; //基础矩阵
        Matrix ans=Matrix_Quick_Pow(x, n-1);
        return ans.a;
    }
};