细说斐波那契数列的四种代码实现
关于斐波那契数列的背景相信⼤家都有所⽿闻，不知道的可以去搜索⼀下兔⼦问题。在⼤多数的应⽤场合，没有⼈会直接让你编写⼀段代码实现斐波那契数列，⽽会把他装在⼀个应⽤场景中，这个场景可以是兔⼦⽣兔⼦，也可以是青蛙爬楼梯，⽐起学会如何实现它，⼤家更需要掌握的技能是，看到应⽤场景可以反映出这实际上是⼀个斐波那契问题。毕竟如何实现斐波那契，⽹上的教程⼀搜⼀堆，但判断当前问题可不可以⽤斐波那契思想解决，需要你的判断才⾏。
⾔归正传，该问题的四种代码实现分别为 递归法、迭代法、通项公式法和矩阵法，后两种⽅法对于线性代数基础薄弱的⼈来说可能不太好理解，但是学会了它受益良多，还是建议⼤家能够掌握。
⼀、递归法
递归解决斐波那契问题虽然很直观，但存在的问题是时间复杂度太⾼（重复计算太多），所以给出代码各位看看就好。
class Solution {
public int climbStairs(int n) {
if(n == 0) return 0;
el if(n == 1) return 1;
el return climbStairs(n - 1) + climbStairs(n - 2);
}
⼆、迭代法
这⾥利⽤了动态规划的思想，从公式可以看出，当前的状态等于前⼀时刻的状态+前两时刻的状态，我们知道了第0时刻和第1时刻，递推就可以得到结果啦，显然时间复杂度为o(n)。
class Solution {
public int climbStairs(int n) {
int fibNOne = 1, fibNTwo = 0, fibN = 0;
for (int i = 1; i <= n; ++i) {
fibN = fibNOne + fibNTwo;
fibNTwo = fibNOne; //前两时刻
fibNOne = fibN; //前⼀时刻春水春池满
}
return fibN;
}
}
三、通项公式
如何瘦脸其实递归法已经⾜够好了，但是精益求精的我们会琢磨有没有时间复杂度更快地⽅法呢，还真有，o(logn)。
我们⾸先需要了解齐次线性递推公式的特征⽅程：
对于形如： 的递推式，可得结论：
1）其递推⽅程为
2）
谢谢英文
故⽽由斐波那契数列可得齐次线性⽅程，解⽅程可得 ,
由 , ，可得
此时f(n)直接可求。
class Solution {
public int climbStairs(int n) {
return (int)((Math.pow((1+Math.sqrt(5))/2,n)-Math.pow((1-Math.sqrt(5))/2,n))/Math.sqrt(5));
}
}
这段代码的实现之所以是o(logn)原因就在于Math.pow这个函数，下⾯我们讲解⼀下这个函数的实现原理：
pow【快速幂算法】本质上是⼀个分治算法，故⽽时间复杂度是o(logn)。我们求实际上是在前⼀个结果的基础上进⾏平⽅操作。我们找到了问题的重复⼦问题，⾃然⽽然可以想到递归操作。有某些时刻，平⽅后的结果还需再乘上⼀个x。判断是否需要额外乘x的⽅法很简单，就是当n为奇数时，结果的平⽅需再乘以⼀个x。具体实现如下：
class Solution {
public double myPow(double x, int n) {
return n<0 ? 1/dfs(x, n) : dfs(x,n);
}
public double dfs(double x, int n) {
if(n==0) return 1.0;
double y = dfs(x,n/2);
return n%2==0 ? y*y : y*y*x;
}
}
另⼀个⽐较巧妙地思路是利⽤⼆进制位算法，我们利⽤规律：
则
具体实现如下：
lass Solution {
public double pow(double x, long n) {
double res = 1.0;
double x_contribution = x;
while(n>0) {
if((n&1)==1) res*=x_contribution;
x_contribution *= x_contribution;
编辑的工作内容
n=n>>1;
}
return res;
}
public double myPow(double x, int n) {
long b = n; //防⽌执⾏n=-n时数组越界
return b<0 ? 1.0/pow(x,-b) : pow(x,b);
}
}
四、矩阵快速幂
第三种⽅法中的根号和除法会存在计算精度的问题。受到快速幂算法的启发，如果可以把求解过程转化为求解n次幂，那问题便可迎刃⽽解。这就要⽤到线性代数的知识了。
我们知道对于斐波那契数列，状态是这样转移的：冲绳人
功败垂成的意思
填0变成矩阵，则可得⽅程：
推导出：
此时求f(n)的问题便转化成了⼀个求矩阵n次幂的问题：
class Solution {
public int climbStairs(int n) {牛腩土豆的做法
int[][] q = {{0,1},{1,1}};
int[][] res = myPow(q,n);
return res[1][0];
}
public int[][] myPow(int[][] q, int n) {
int[][] res = {{1,0},{0,1}};
int[][] x_contribution = q;
if(n==0) return new int[2][2];薪尽火传
while(n>0) {
if((n&1)==1) res = multiple(res, x_contribution);
n = n>>1;
x_contribution = multiple(x_contribution,x_contribution); }
return res;
}
public int[][] multiple(int[][] a, int[][] b) {
int[][] c = new int[2][2];
for(int i=0;i<2;i++) {
for(int j=0;j<2;j++) c[i][j] = a[i][0]*b[0][j]+a[i][1]*b[1][j];
}
return c;
}
}
