13-类似斐波那契数列的递归

求斐波那契数列方法的优化

线性求解

斐波那契数列的线性求解（O(N)）的方式非常好理解。

F_k+2 =F_k+1+F_K

//线性计算
	public static int f2(int n) {
		if (n < 1) {
			return 0;
		}
		if (n == 1 || n == 2) {
			return 1;
		}
		int res = 1;
		int pre = 1;
		int tmp = 0;
		for (int i = 3; i <= n; i++) {
			tmp = res;
			res = res + pre;
			pre = tmp;
		}
		return res;
	}

递归

递归实现也简单

//暴力递归
	public static int f1(int n) {
		if (n < 1) {
			return 0;
		}
		if (n == 1 || n == 2) {
			return 1;
		}
		return f1(n - 1) + f1(n - 2);
	}

线性代数的实现

但对此问题我们可以有**时间复杂度O(logN)**的方法，即利用线性代数。

结论为：| F(N) , F(N-1) | = | F(2) , F(1) | * 某个二阶矩阵的N-2次方

过程推导可看此知乎文章：https://zhuanlan.zhihu.com/p/125779602

有结论可知，我们需要求一个矩阵的N-2次方。

那么，数和矩阵的N次方怎么算最快?

比如$10^{75}$次方怎么算最快?

75 的 二进制 = 1001011

那么$10^{75}$=$10^{1}$* $10^{2}$ * $10^{8}$ * $10^{64}$

所有我们可以取次方的二进制，对位进行0,1判断，然后乘入结果。

跟自己玩 $logN$次，需要的时候乘进来，不需要的时候不乘，最多再来一个$logN$次

代价最多就是$2logN$次, 所以复杂度就是$O(logN)$

这个思想的基础是二分

那么矩阵的求解也可以根据此思想来。

所以代码如下：

	public static int f3(int n) {
		if (n < 1) {
			return 0;
		}
		if (n == 1 || n == 2) {
			return 1;
		}
		// [ 1 ,1 ]
		// [ 1, 0 ]
		int[][] base = { 
				{ 1, 1 }, 
				{ 1, 0 } 
				};
		int[][] res = matrixPower(base, n - 2);
		return res[0][0] + res[1][0];
	}

	public static int[][] matrixPower(int[][] m, int p) {
		int[][] res = new int[m.length][m[0].length];
		for (int i = 0; i < res.length; i++) {
			res[i][i] = 1;
		}
		// res = 矩阵中的1
		int[][] t = m;// 矩阵1次方
		for (; p != 0; p >>= 1) {
			if ((p & 1) != 0) {
				res = product(res, t);
			}
			t = product(t, t);
		}
		return res;
	}

	// 两个矩阵乘完之后的结果返回
	public static int[][] product(int[][] a, int[][] b) {
		int n = a.length;
		int m = b[0].length;
		int k = a[0].length; // a的列数同时也是b的行数
		int[][] ans = new int[n][m];
		for(int i = 0 ; i < n; i++) {
			for(int j = 0 ; j < m;j++) {
				for(int c = 0; c < k; c++) {
					ans[i][j] += a[i][c] * b[c][j];
				}
			}
		}
		return ans;
	}

类似斐波那契数列的递归优化

斐波那契数列的求解能使用这种方法优化，那么与其类似的也可以使用。

如果某个递归，除了初始项之外，具有如下的形式

F(N) = C1 * F(N) + C2 * F(N-1) + … + Ck * F(N-k) ( C1…Ck 和k都是常数)

并且这个递归的表达式是严格的、不随条件转移的

那么都存在类似斐波那契数列的优化，时间复杂度都能优 O(logN)

例题1：母牛生小牛, N年后牛的数量

第一年农场有1只成熟的母牛A，往后的每年：

1. 每一只成熟的母牛都会生一只母牛
2. 每一只新出生的母牛都在出生的第三年成熟
3. 每一只母牛永远不会死

返回N年后牛的数量。

思路

由题目的信息，并且推导可得

F(N)=1*F(N-1 )+ 0 * F(N-2) + 1 * F(N-3)

| F(N) , F(N-1) , F(N-2) | = | F(3) , F(2) , F(1) | * 某个三阶矩阵的N-3次方

这个三阶矩阵如何求？

$$\left[ \begin{matrix} a & b & b \\ d & e & f \\ g & h & i \end{matrix} \right] \tag{3}$$

和之前的类似

|F₄F₃F₂|= |F₃F₂F₁| * 3阶矩阵

|F₅F₄F₃|= |F₄F₃F₂| * 3阶矩阵

…

因为F1,F2,F3…都是已知的，

所以我们可以求得 3阶矩阵为

$$\left[ \begin{matrix} 1 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{matrix} \right] \tag{3}$$

然后根据上面$O(logN)$时间复杂度的，计算次方的方法，算出3阶矩阵的N-3次方。

且因为| F(N) , F(N-1) , F(N-2) | = | F(3) , F(2) , F(1) | * 某个三阶矩阵的N-3次方

所以可得F(N)的值

例题2：一个人迈上N级台阶的方法数

一个人可以一次往上迈1个台阶，也可以迈2个台阶

返回这个人迈上N级台阶的方法数

例题3：由0和1两种字符构成的达标字符串

给定一个数N，想象只由0和1两种字符，组成的所有长度为N的字符串

如果某个字符串,任何0字符的左边都有1紧挨着,认为这个字符串达标

返回有多少达标的字符串

例题4：铺瓷砖问题

你有无限的1 x 2的砖块，要铺满2 x N的区域，不同的铺法有多少种?

你有无限的1 x 2的砖块，要铺满M x N的区域，不同的铺法有多少种?