14-《进阶》斐波那契数列相关的递归.md

[TOC]
# 1 类似斐波那契数列的递归

## 1.1 求斐波那契数列矩阵乘法的方法

1、菲波那切数列的线性求解（O(N)）的方法非常好理解（一次遍历，N项依赖于N-1项和N-2项）

2、同时利用线性代数，也可以改写出另外一种表示`|F(N),F(N-1)| = |F(2),F(1)| * 某个二阶矩阵的N-2次方`

3、求出这二阶矩阵，进而最快求出这个二阶矩阵的N-2次方


## 1.2 菲波那切数列可优化为O(logN)时间复杂度

### 1.2.1 矩阵加快速幂方法

#### 1.2.1.1 矩阵推导

> 由于菲波那切数列是一个严格的递推式，不会发生条件转移。

> 在线性代数中，对于（严格递推式）菲波那切数列，第二项和第三项所组成的行列式，等于第二项和第一项组成的行列式，乘以某一个2乘2的矩阵

> 同理第四项和第三项行列式等于第三项和第二项组成的行列式乘以相同的矩阵，其他同理

```math
|F(3),F(2)| = |F(2),F(1)| *  \left\{ \begin{matrix} a & b \\ c & d \end{matrix} \right\}

|F(4),F(3)| = |F(3),F(2)| *  \left\{ \begin{matrix} a & b \\ c & d \end{matrix} \right\}
```

举例：例如1 1 2 3 5 8 ... 的菲波那切数列，我们带入公式

```math
|2,1| = |1,1| * \left\{ \begin{matrix} a & b \\ c & d \end{matrix} \right\}

=> 2 = 1 * a + 1 * c

=> 1 = 1 * b + 1 * d

=> a + c = 2; b + d = 1; 


|3,2| = |2,1| * \left\{ \begin{matrix} a & b \\ c & d \end{matrix} \right\}

=> 2a + c = 3; 2b + d =2;


=> a=1; b=1; c=1; d=0;

```

可以得到我们的相同二阶矩阵中，a=1; b=1; c=1; d=0;


> 继续推导，由于我们的严格递推式满足，我们可以把f(3)f(2)的公式带入到f(4)f(3)中，以此替换到f(n)f(n-1) = f(n-1)f(n-2) * 固定矩阵中

继续推导得出：

```math
|F(N) * F(N-1)| = |F(2)F(1)| * \left\{ \begin{matrix} a & b \\ c & d \end{matrix} \right\}^{n-2}
```

> 由于菲波那切数列第二项和第一项是1,1,那么化简后，我们可以得到：f(n)和f(n-1)构成的行列式，等于1,1的行列式，乘以1110构成的矩阵的n-1次方。算该矩阵的n-2次方直接影响我们的算法复杂度。

> 转化为，怎么求多个相同矩阵乘起来，怎么算比较快的问题？我们先思考怎么求一个数乘方怎么算比较快的问题？

#### 1.2.1.2 快速幂转化思路

问：怎么快速求出10的75次方的值是多少。

> 思路：利用一种精致的二分来求，75次方我们拆分成二进制形式，1001011

```math
10^{75} = 10^{64} * 10^8 * 10^2 * 10^1
```

我们先从10的1次方开始，用tmp中间变量接收，依次和我们指数的二进制做比较。如果指数的二进制某一位为1，我们就要乘我们的t当成我们的result（初始为1），如果为0，我们就不乘。tmp每次判断结束和自身相乘，生成新的tmp。最终result就是我们的结果

> 10的75次方推演为:tmp为10开始，对比二进制，需要乘进result。tmp和自己相乘变为10^2，仍然需要，result为1乘10乘10的平方乘10的八次方...。tmp虽然在变化，但我们不是都选择相乘


所以上述矩阵次方的乘法，我们可以类似处理。把指数变为二进制。result初始值为单位矩阵，就是对角线全为1的矩阵。其他处理和数字次方的处理类似


**在JDK中，Math.power函数的内部，也是这样实现指数函数的（整数次方）**


## 1.3 递推推广式

如果某一个递推式，`F(N) = c1F(n-1) + C2F(n-2) + ... + czF(N-k)` k表示最底层减到多少，我们称之为k阶递归式。c1,c2,cz为常数系数，k为常数，那么都有O(logN)的解。系数只会影响到我们的k阶矩阵的不同

奶牛问题：

一个农场第一年有一只奶牛A，每一只奶牛每年会产一只小奶牛。假设所有牛都不会死，且小牛需要三年，可以产小奶牛。求N年后牛的数量。

> 思路：牛的数量的轨迹为：1,2,3,4,6,9...。`F(N) = F(N-1) + F(N-3)` 既今年的牛F(N)等于去年的牛F(N-1) + 三年前牛的数量F(N-3)。三阶问题k=3。

> 套上述公式为: `F(N) = 1 * F(N-1) + 1 * 0 * F(N-2) + 1 * F(N-3)` 

> 对于三阶问题，可以写成：**`|F(n)F(n-1)F(n-2)| = |F3F2F1| * |3*3|^{n-3}`**

通用的表达式如下，同理根据前几项，求出原始矩阵。

```
|F(n)F(n-1)...F(n-k+1)| = |Fk...F2F1| * |k*k|^{n-k}
```


```Go
package main

import "fmt"

// 斐波那契数列暴力解法
func f1(n int) int {
	if n < 1 {
		return 0
	}

	if n == 1 || n == 2 {
		return 1
	}

	return f1(n-1) + f1(n-2)
}

// 斐波那契数列线性求解方法
func f2(n int) int {
	if n < 1 {
		return 0
	}

	if n == 1 || n == 2 {
		return 1
	}

	res := 1
	pre := 1
	tmp := 0

	for i := 1; i <= n; i++ {
		tmp = res
		res = res + pre
		pre = tmp
	}

	return res
}

// 斐波那契矩阵加快速幂O(logN)方法
func f3(n int) int {
	if n < 1 {
		return 0
	}

	if n == 1 || n == 2 {
		return 1
	}

	// [ 1 ,1 ]
	// [ 1, 0 ]
	base := [][]int{
		{1, 1},
		{1, 0},
	}
	// 求出base矩阵的n-2次方，得到的矩阵返回
	res := matrixPower(base, n-2)
	// 最终通过单位矩阵乘以该res，矩阵运算后返回fn的值。
	// 得到xyzk组成的矩阵
	// f(n)F(n-1) =   {1, 0}  *  {x, y}
	//                {0, 1}     {z, k}
	// 推导出fn = x + z
	return res[0][0] + res[1][0]
}

// 快速求一个矩阵m的p次方
func matrixPower(m [][]int, p int) [][]int {
	res := make([][]int, len(m))
	for i := 0; i < len(res); i++ {
		res[i] = make([]int, len(m[0]))
	}

	for i := 0; i < len(res); i++ {
		// 单位矩阵，对角线都是1。相当于矩阵概念中的'1'
		res[i][i] = 1
	}

	// res = 矩阵中的1
	tmp := m // 矩阵1次方
	// 基于次方的p，做位运算。右移
	for ; p != 0; p >>= 1 {
		// 右移之后的末位不是0，才乘当前的tmp
		if (p & 1) != 0 {
			res = muliMatrix(res, tmp)
		}
		// 自己和自己相乘，得到下一个tmp
		tmp = muliMatrix(tmp, tmp)
	}
	return res
}

// 两个矩阵乘完之后的结果返回
func muliMatrix(m1 [][]int, m2 [][]int) [][]int {
	res := make([][]int, len(m1))
	for i := 0; i < len(res); i++ {
		res[i] = make([]int, len(m2[0]))
	}

	for i := 0; i < len(m1); i++ {
		for j := 0; j < len(m2[0]); j++ {
			for k := 0; k < len(m2); k++ {
				res[i][j] += m1[i][k] * m2[k][j]
			}
		}
	}
	return res
}

// 奶牛问题O(logN)
func s3(n int) int {
	if n < 1 {
		return 0
	}

	if n == 1 || n == 2 {
		return n
	}

	base := [][]int{
		{1, 1},
		{1, 0},
	}

	res := matrixPower(base, n-2)
	return 2*res[0][0] + res[1][0]
}

// 奶牛问题暴力递归
func c1(n int) int {
	if n < 1 {
		return 0
	}
	if n == 1 || n == 2 || n == 3 {
		return n
	}

	return c1(n-1) + c1(n-3)
}

// 奶牛问题线性解
func c2(n int) int {
	if n < 1 {
		return 0
	}
	if n == 1 || n == 2 || n == 3 {
		return n
	}
	res := 3
	pre := 2
	prepre := 1
	tmp1 := 0
	tmp2 := 0
	for i := 4; i <= n; i++ {
		tmp1 = res
		tmp2 = pre
		res = res + prepre
		pre = tmp1
		prepre = tmp2
	}
	return res
}

// 奶牛问题矩阵解
func c3(n int) int {
	if n < 1 {
		return 0
	}
	if n == 1 || n == 2 || n == 3 {
		return n
	}

	// 原始矩阵
	base := [][]int{
		{1, 1, 0},
		{0, 0, 1},
		{1, 0, 0},
	}
	res := matrixPower(base, n - 3)
	return 3 * res[0][0] + 2 * res[1][0] + res[2][0]
}

func main() {
	n := 19
	fmt.Println(f1(n))
	fmt.Println(f2(n))
	fmt.Println(c1(n))
	fmt.Println(c3(n))
}
```

## 1.4 迈楼梯问题

问题描述：小明想要迈到n层台阶上去，可以一次迈一层台阶，可以一次迈两层台阶。问：迈到n层一共可以有多少种方法

> 思路：1层台阶的时候，只有一种方法。2层台阶的时候迈两次一步1中，一次迈两步1种共两种方法。n层台阶等于迈到n-1层的方法数，加上迈到n-2层台阶的方法数

```math
F(N) = F(n-1) + F(n-2)
```

**二阶递推式，类似菲波那切数列问题，区别在与斐波那契数列的初始值为1,1,而本题的初始值为1,2而已**


问题升级：同样条件，可以迈1步，可以迈2步，可以迈5步，问迈到n层台阶，有多少种方法


```math
F(N) = F(n-1) + F(n-2) + F(n-5)
```

**五阶递推，求5乘5的原始矩阵即可，拿到矩阵表达式**


问题升级：奶牛问题，假设原有条件不变的情况下，奶牛寿命为10年

```math
F(N) = F(n-1) + F(n-3) - F(n-10)
```

**十阶递推，求10乘10的原始矩阵，拿到矩阵关系表达式**

每年，这种问题在面试笔试中大量出现，兔子生乌龟问题，乌龟生兔子问题，等等，层出不穷，都可以用这种方法模型求解

## 1.5 递推经典例题一

题目描述：给定一个数N,想象只有0和1两种字符，组成的所有长度为N的字符串。如果某个字符串，任何0字符的左边都有1紧挨着，认为这个字符串达标，返回有多少达标的字符串


> 思路：N=1时，有0和1组成的01字符只有0或者1。单个字符'0'不达标，只有'1'一种达标的字符串

> N=1时，有0和1组成的01字符有四种'00','01','10','11'。'10'和'11'达标，两个

> N=3时，有0和1组成的01字符有八种。达标的为'101','110','111'三个

> 暴力解为O(2^n * n)。优化：我们定义一个i长度的字符串，该字符串最左边一定是'1'。在i长度上自由变换，最终有多少个达标的。如果n=8,由于最左侧已经规定了'1'，我们调用f(7),在这7个位置的第一个位置判断，如果1位置是0,2位置必定不能为0，为1。那么f(i-2)长度可以任意变。如果第一个字符填的是1，那么f(i-1)可以随意变。衍生出菲波那切数列的递推公式；**二阶递推**


```math
f(i) = f(i-1) + f(i-2)
```

## 1.6 递推经典例题二

题目描述：有一款2行，N列的区域。假设我们只有1*2大小的瓷砖，我们把该区域填满有多少种方案？

> 思路：定义F(N)函数，返回2*N区域都没贴瓷砖的会有多少种方法数。

> 第一块瓷砖竖着拜，剩下的区域有F(N-1)种，第一块瓷砖横着摆，第一块瓷砖下方区域只能横着摆，剩下的方法数自由摆放为F(N-2)

```math
F(N) = F(N-1) + F(N-2)
```

**仍然是一个二阶递推式，菲波那切数列问题**

菲波那切数列问题及其推广，适用递推的限制为：**严格的，没有条件转移的递推**