斐波那契数列来源于兔子繁殖问题，所以也叫兔子序列。

  最开始我一直不能理解兔子问题怎么和斐波那契数列联系在一起的，然后画了这个图之后，就明白了。
  第一年有一对小兔子，一年后成年。成年的兔子又可以生出一对小兔子，如此循环往复，每年的兔子数就构成了一个斐波那契数列。
  斐波那契数列有很多马甲：

• 爬楼梯问题，一次可以爬一级，也可以爬两级；
• 用1个2 * 1个小矩形覆盖8个2*1的小矩形问题（剑指offer）。

  有四种解决方法：

1. 递归

  这是最简单，也是效率最差的一种：

    public long recursive(int n) {
        if (n <= 0) return 0;
        if (n == 1) return 1;
        return recursive(n - 1) + recursive(n - 2);
    }
复制

   时间复杂度指数级，他的递归通项公式可以转换为一个齐次二阶常系数差分方程：
      设f(n)为参数为n时的时间复杂度，很明显：f(n)=f(n-1)+f(n-2) ，且f(0)=0; f(1)=1;
      特征方程为：x^2-x-1=0
      得 x=(1±√5)/2
      因而f(n)的通解为:
           
      由f(0)=0; f(1)=1可解得c_1，c_2
      最终可得，时间复杂度为：
           
   真是没想到，高数里的差分方程在这里用到了，说真的，我刚看到这里还挺惊喜的。

2. 数学公式法

   有了上述时间复杂度的分析，就可以直接套用最后得出的公式，直接利用给的n计算x，时间复杂度O（logn）。因为涉及到幂运算。

3. 动态规划

   利用动态规划的思想，利用递归分析问题，找到状态转移方程，然后从第一个状态开始迭代到最终状态。

这里的状态转移方程是：f(n) = f(n - 1) + f(n - 2)   (n > 2)
初始状态：f(0) = 0; f(1) = 1;

    public long addition(int n) {
        int[] result = {1, 2};
        if (n < 2) {
            return result[n];
        }
        long n1 = 0;
        long n2 = 1;
        long n3 = 0;
        for (int i = 2; i <= n; i++) {
            n3 = n1 + n2;
            n1 = n2;
            n2 = n3;
        }
        return n3;
    }
复制

4. 矩阵乘法

   根据这个公式写代码算就完事了。

let matrix22_mul = (x, y) = >{
	[x[0][0] * y[0][0] + x[0][1] * y[1][0], x[0][0] * y[0][1] + x[0][1] * y[1][1],
	 x[1][0] * y[0][0] + x[1][1] * y[1][0], x[1][0] * y[0][1] + x[1][1] * y[1][1]]
}
let matrix22_pow = (x, n) =>{
	var r = [[1,0],[0,1]];
	var v = x;
	while (n) {
		if (n % 2 == 1) {
			r = matrix22_mul(r, v);
			n -= 1;
		}
		v = matrix22_mul(v, v);
		n = n / 2;
	}
	return r;
}
let fibnacci = n => n <= 0 ? 0 : 
				    matrix22_mul([[0,1],[0,0]], matrix22_pow([[0,1],[1,1]], n - 1))[0][1];
复制

   看到winter大神写的代码，待我理解理解后面转为java，再来修改。

推荐内容