0%

递归和动态规划

发表于 更新于 分类于
本文字数： 阅读时长 ≈

1，斐波那契数列问题的递归和动态规划
补充题目1：
给定整数n，代表台阶数，1次可以跨2个或者1个台阶，返回有多少种走法。
举例：n=3，可以三次都跨一个台阶；也可以先跨2个台阶，再跨一个台阶；还可以先跨1一个台阶，再跨两个台阶。所以有三种方法。

补充题目2：假设母牛每年生1头小母牛，并且永远不会死。第一年有1只成熟的母牛，从第二年开始，母牛开始生小牛。每只小母牛3年之后成熟又可以生小母牛。给定整数n，求出n年后的数量。
举例：n=6，第一年1头母牛记为a；第二年a生了新的小母牛，记为b，总数为2；第三年a生了新的小母牛，记为c，总牛数为3；第4年a生了新的小母牛，记为d，总数为4。第五年b成熟了，a和b分别生了新的小母牛，总数为6；第6年c也成熟了，a、b和c分别生了新的小母牛，总数为9，返回9。
要求：时间复杂度O(logn)。
原问题的解答：
    很容易写出暴力递归的解法,时间复杂度为O(2的n次方)。
    代码如下：
1
2
3
4
5
6
7
8
9
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(n)复杂度的方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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)时间复杂度的方法。
分析：用矩阵乘法的方式可以将时间复杂度降为O(logn)。f(n) = f(n-1) + f(n-2)，是一个二阶递推数列，一定可以用矩阵乘法的形式表示，且状态矩阵为2*2的矩阵(这个太难，暂时理解不了)。
补充问题1：台阶只有1个，走法只有一种，有两个方法2种，如果有n级，最后跳上第n级的情况，要么是从n-2级台阶直接跨2级台阶，要么是n-1级跨1级台阶，所以台阶有n级的方法数，为跨到n-2级台阶的方法数加上跨到n-1级台阶的方法数，即s(n) = s(n-1) + s(n-2)，初始项s(1) = 1,s(2) = 2，所以类似于斐波那契数列，但是不同的是初始项不同，可以很轻易地写出2的n次方与O(n)的方法，请看下面的s1方法和s2方法。

1
2
3
4
5
6
7
8
9
10
public static int s1(int n) {
		if (n < 1) {
			return 0;
		}
		if (n == 1 || n == 2) {
			return n;
		}
		return s1(n - 1) + s1(n - 2);
		
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int s2(int n) {
		if (n < 1) {
			return 0;
		}
		if (n == 1 || n == 2) {
			return n;
		}
		int res = 2;
		int pre = 1;
		int tmp = 0;
		for (int i = 3; i <= n; i++) {
			tmp = res;
			res = res + pre;
			pre = tmp;
		}
		return res;
}

以上是2的n次方和O(n)复杂度的方法。
下面讲解O(logn)复杂度的方法，也是求状态矩阵，用矩阵乘法。
补充问题2：所有的牛都不会死，c(n) = c(n-1) + c(n-3)。与斐波那契数列类似，不过是c(n)项依赖于c(n-1)和c(n-3)项的值，而斐波那契数列依赖于f(n-1)和f(n-2)项的值。
c1和c2方法分别是2的n次方和O(n)时间复杂度的方法。

1
2
3
4
5
6
7
8
9
public static int c1(int n) {
		if (n < 1) {
			return 0;
		}
		if (n == 1 || n == 2 || n == 3) {
			return n;
		}
		return c1(n - 1) + c1(n - 3);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static int c2(int n) {
		if (n < 1) {
			return 0;
		}
		if (n == 1 || n == 2 || n == 3) {
			return n;
		}
		int res = 3;
		int pre = 2;
		int prepre = 1;
		int tmp1 = 0;
		int tmp2 = 0;
		for (int i = 4; i <= n; i++) {
			tmp1 = res;
			tmp2 = pre;
			res = res + prepre;
			pre = tmp1;
			prepre = tmp2;
		}
		return res;
}