|
类似斐波那契数列的递归优化
如果某个递归，除了初始项之外，具有如下的形式
F(N) = C1 * F(N) + C2 * F(N-1) + … + Ck * F(N-k) ( C1…Ck 和k都是常数)
并且这个递归的表达式是严格的、不随条件转移的
那么都存在类似斐波那契数列的优化，时间复杂度都能优化成O(logN)
题目一
?斐波那契数列矩阵乘法方式的实现
//递归实现
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);
}
//迭代方式
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;
}
// 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 = muliMatrix(res, t);
}
t = muliMatrix(t, t);
}
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;
}
题目二
一个人可以一次往上迈1个台阶，也可以迈2个台阶
返回这个人迈上N级台阶的方法数
第n阶可以从n-1阶台阶到达，也可以从n-2阶台阶到达：
F（n）=F（n-1）+F（n-2）
?题目三
第一年农场有1只成熟的母牛A，往后的每年：
1）每一只成熟的母牛都会生一只母牛
2）每一只新出生的母牛都在出生的第三年成熟
3）每一只母牛永远不会死
返回N年后牛的数量
n年的牛由n-1年牛的个数+n-3年牛个数（满三年都生一只小牛）
F（n）=F（n-1）+F（n-3）
题目四
给定一个数N，想象只由0和1两种字符，组成的所有长度为N的字符串
如果某个字符串,任何0字符的左边都有1紧挨着,认为这个字符串达标
返回有多少达标的字符串
n位数，最左边一位为1有：F（n-1）种方法；最左边为0则倒数第二位必须为1，则有F（n-2）种方法
F（n）=F（n-1）+F（n-2）
题目五
?用1*2的瓷砖，把N*2的区域填满
返回铺瓷砖的方法数
第一个瓷砖竖着排，则后面有F（n-1）种方法；第一个瓷砖横着排，则后面有F（n-2）种方法
F（n）=F（n-1）+F（n-2）
|