题目

给定整数N，返回斐波那契数列的第N项。

1
2
3
4
5
6
7
8
9
public int f1(int n) {
	if (n < 1) {
	return 0;
	}
	if (n == 1 || n == 2) {
	return 1;
	}
	return f1(n - 1) + f1(n - 2);
}

上面的时间复杂度是O(2^N)
要求：时间复杂度O(logN)的解法

思路

由递推公式f(n),f(n-1))=(f(n-1),f(n-2)可以化作

当含有f(n-3)时，行列式是3阶的
可以代入求出行列式

于是有


…
依次带入得到

因此该题目的关键是求行列式的幂运算
集合的幂运算和普通数字的目运算相同，都可以是用二分法
假设有整数是10，如何最快的求解10的75次方。

  1. 75的2进制形式为1001011。
  2. 10的75次方=(10^64) (10^8) (10^2) * (10^1)。在这个过程中，我们先求出10^1，然
    后根据10^1求出10^2，再根据10^2求出10^4， …，最后根据10^32求出10^64次方，即75的
    ⼆进制形式总共有多少位，我们就使用了几次次乘法。
  3. 在步骤2的过程中，把应该累乘的值乘起来即可。 10^64、 10^8、 10^2、 10^1应该累
    乘起来，因为64、 8、 2、 1对应到75的2进制中，相应的位上是1。而10^32、 10^16、 10^4
    不应该累乘，因为32、 16、 4对应到75的2进制中，相应的位上是0。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    //整数的幂运算
    public  static int power(int x, int n)
    {
    	if (n == 0)
    		return 1;
    	int result = 1;
    	while (n != 0)
    	{
    		//n%2 != 0
    		if ((n & 1) != 0)
    			result *= x;
    		x *= x;
    		//n/=2
    		n >>= 1;
    	}
    	return result;
    }

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// 计算矩阵的幂运算
public static int[][] matrixPower(int[][] m, int p) {
	int[][] res = new int[m.length][m[0].length];
	// 初始化结果矩阵为单位阵，即对角线是1，其余位置是0，相当于整数中的1
	//相当于设置res=1
	for (int i = 0; i < m.length; i++) {
		res[i][i] = 1;
	}
	int[][] tmp = m;
	while (p != 0) {
		if (p % 2 != 0) {
			res = muliMatrix(res, tmp);
		}
		tmp = muliMatrix(tmp, tmp);
		p /= 2;
	}
	return res;
}
// 矩阵相乘的运算
public static int[][] muliMatrix(int[][] m1, int[][] m2) {
	int[][] res = new int[m1.length][m2[0].length];
	for (int i = 0; i < m1.length; i++) {
		for (int j = 0; j < m2[0].length; j++) {
			for (int k = 0; k < m2.length; k++) {
				res[i][j] += m1[i][k] * m2[k][j];
			}
		}
	}
	return res;
}
public static int f(int n) {
	if(n < 1){
		return 0;
	}else if(n == 1 || n == 2){
		return 1;
	}else{
		
		int[][] a = {{1, 1}, {1, 0}};
		int[][] res = matrixPower(a, n-2);
		return res[0][0] + res[1][0];
	}
}

题目

假设农场中成熟的母牛每年只会生1头小母牛，并且永远不会死。第一年农场有1只成熟的母牛，从第二年开始，母牛将开始生小母牛。每只小母牛3年之后成熟又可以开始生小母牛。给定整数N，求出N年后牛的数量。

N=6。第1年1头成熟母牛记为a。第2年a生了新的小母牛记为b，总牛数为2。第3年a生了新的小母牛记为c，总牛数为3。第4年a生了新的小母牛记为d，总牛数为4。第5年b成熟了，a和b分别生了新的小母牛，总牛数为6。第6年c也成熟了，a、b和c分别生了新的小母牛，总牛数为9。返回9。

思路

递推公式为C(n)=C(n-1)+C(n-3)，C(1)=1， C(2)=2， C(3)=3， C(4)=4， C(5)=6
因此可以化为3阶

带入求解的到

代码

1
2
3
4
5
6
7
8
9
10
11
public int c(int n) {
	if (n < 1) {
		return 0;
	}
	if (n == 1 || n == 2 || n == 3) {
		return n;
	}
	int[][] base = { { 1, 1, 0 }, { 0, 0, 1 }, { 1, 0, 0 } };
	int[][] res = matrixPower(base, n - 3);
	return 3 * res[0][0] + 2 * res[1][0] + res[2][0];
}

结论

如果递归式严格符合F(n)=aF(n-1)+bF(n-2)+…+kF(n-i)，那么它就是i阶的递推式，必
然有与ii的状态矩阵有关的矩阵乘法的表达。一律可以用加速矩阵乘法的动态规划将时间复
杂度降为O(logN)。