有一座高度是1000级台阶的天梯,从下往上走,每跨一步只能向上1级或者2级台阶。要找出一共有多少种走法?
解题思考
如题1000级台阶着实有点多了,我们先来思考6级阶梯的情况,共13种
- 🏃 1+1+1+1+1+1
- 🏃 1+1+1+1+2
- 🏃 1+1+1+2+1
- 🏃 1+1+2+1+1
- 🏃 1+2+1+1+1
- 🏃 2+1+1+1+1
- 🏃 1+1+2+2
- 🏃 1+2+1+2
- 🏃 1+2+2+1
- 🏃 2+1+1+2
- 🏃 2+1+2+1
- 🏃 2+2+1+1
- 🏃 2+2+2
在仅有6级阶梯的情况下穷举已经有一些费力了,如果是1000级那几乎不可能穷举了,我们要思考找出其中的微妙之处。
现在我们假设只差最后一步就能达到第6级阶梯了,那么会出现几种情况?无非就是从第5级花费一步或者从第4级花费两步跳到第6级阶梯,我们现在假设0-4级阶梯有X种走法,0-5级阶梯有Y种走法,那么0-6级阶梯的走法有多少种?
🏃差一步 | ==6级== | ||||
🏃差两步 | ==5级== | ?种走法🐴 | |||
==4级== | Y种走法🐴 | ||||
==3级== | X种走法🐴 | ||||
==2级== | |||||
==1级== | |||||
我们来分析一下,要走到第6级阶梯最后一步必然从4或5级阶梯开始的,而4或5级阶梯我们知道它的走法为X与Y,那么显然0-6级阶梯的走法即为X+Y,这个时候我们可以发现,每一级阶梯的走法数目其实都是由它的前两级阶梯来决定的,即可用此函数表示
fun(N) = func(N - 1) + func(N - 2)
且我们知道第1级的阶梯有一步走法,第二级的阶梯有两步走法,所以函数完整的表示为
func(1) = 1
func(2) = 2
fun(N) = func(N - 1) + func(N - 2)
这种解题思路即是动态规划思想,将大事化小,小事化了,转换为简单的问题,其中最后一步必然从4或5级阶梯开始这个称之为最优子结构,上述的方程称之为状态转移方程,func(1|2)称之为边界。
编码实现
递归实现
上述的方程随眼一看即知道,这是一个递归方程,现在我们使用递归编程来实现此题的解法。
public int getStairsWays(int n) {
if (n <= 0) {
return 0;
}
if (n == 1 || n == 2) {
return n;
}
return getStairsWays(n - 1) + getStairsWays(n - 2);
}
其实稍微计算一下这套实现的时间复杂度你就会发现非常恐怖,它的计算量相当于一个二叉树,时间复杂度达到了O(2^N),空间复杂度为O(1)。这道题目的优化空间是很大的,我们首先思考一下它的计算过程,我们可以发现很多都是重复计算的
func(5) = func(4) + func(3)
func(4) = func(3) + func(2)
func(3) = func(2) + func(1)
func(3)被重复计算了很多次,为了降低计算次数,我们可以将已经计算过的缓存起来,不去重新计算它。
备忘录算法
备忘录算法是递归实现了一种改良版,使用了一块内存区域来存储已经计算过的阶梯数,防止重复计算,在这里使用的是HashMap对象,其实更优的选择应该是一个长度为阶梯高度的int数组。
public int getStairsWays(int n) {
return getStairsWays(n, null);
}
public int getStairsWays(int n, Map<Integer, Integer> cache) {
if (n <= 0) {
return 0;
}
if (n == 1 || n == 2) {
return n;
}
if (cache == null) { // 初始化一个缓存对象 容量为log(n)的向上取整
cache = new HashMap<>((int) Math.ceil(Math.log(n) / Math.log(2)));
}
if (cache.containsKey(n)) {
return cache.get(n);
}
int value = getStairsWays(n - 1, cache) + getStairsWays(n - 2, cache);
cache.put(n, value);
return value;
}
我们大概看一下这个算法的时间与空间复杂度,备忘录缓存了各级背包的计算结果因此它真正计算的只有n次,时间复杂度为O(N),由于需要内存去缓存计算结果,所以它的空间复杂度也为O(N)
我们可以再分析一下,还有没有更优的解法呢?重新观察我们的计算过程
func(6) = func(5) + func(4)
func(5) = func(4) + func(3)
func(4) = func(3) + func(2)
func(3) = func(2) + func(1)
func(6)只依赖于func(5)与func(4),所以当func(5)与func(4)的结果值出来以后,func(3)这个结果就再没必要缓存了,我们把思维逆转一下,从func(3)开始计算到func(6)。
动态规划算法
这里我们考虑使用自底向上的解法,只需要用两个变量来存储它的两个依赖值,分别是差两步的走法数目(pre)以及差一步的走法数目(next),最终的走法数目为这两个依赖值的和。
public int getStairsWays(int n) {
if (n <= 0) {
return 0;
}
if (n == 1 || n == 2) {
return n;
}
int pre = 1;
int next = 2;
for (int i = 3; i < n; i++) {
int temp = next;
next = pre + next;
pre = temp;
}
return pre + next;
}
分析一下这个算法的时间与空间复杂度,循环n-2次计算,所以时间复杂度是O(N),内存上只开辟了两个临时变量没有额外的内存空间使用,所以空间复杂度为O(1),这就是真正的动态规划算法。
有兴趣的同学可以测试一下以上三个算法在1000个阶梯的量级下运行时间,反正我使用递归运行了一下1000次阶梯,等了十分钟也没结果最终放弃了…
有没有更优解
答案是有的,且时间复杂度为O(logN),有兴趣的可以搜索数论中的矩阵快速幂,可根据状态转移方程快速计算出结果,与动态规划思想结合使用。
还有就是我们来观察上面讲到的状态转移方程,不难看出这表示的是一个斐波那契数列,而斐波那契数列是有通项公式的,在如这种特定问题下可以直接代入通项公式求解。
题目扩展, 背包问题
给定一组多个(n)物品,每种物品都有自己的重量(Wi)和价值(Vi),每种物品至多选择一个,在限定可承受总重量(C)的背包内,要想背包内物品的总价值最高,应该选择那几件物品?
简化题目
我们先假设有5组物品,其中它的价值与重量分别为[4,2,1,3,1]、[4,3,2,1,2],背包可承受总重量为6,求应该选那几件物品使得背包中的物品价值最大?
动态规划思路四步解题
问题是否可拆分?
如爬楼梯问题可以拆分成剩余一步与剩余两步的走法,此问题该如何拆分?
- 我们先针对最后一个物品(价值为1,重量为2)做假设
(1) 装载物品进入背包,问题演变成,有4组物品,背包承重量为4,应该选那几件物品使得背包中的物品价值最大?
(2) 物品不被装载,问题演变成,有4组物品,背包承重量为6,应该选那几件物品使得背包中的物品价值最大?
(3) 接下来我们还可以对子情况(1)、(2)分别做假设,因此该问题是可拆分的。
最优子结构是什么?
如爬楼梯的问题的最优子结构是剩余一步与剩余两步的走法相加,此问题的最优结构是什么?
针对我们刚刚的假设(1)、(2),要想使得背包物品价值最大,最优的结构显而易见是(1)、(2)情况中背包价值更大的那个方案。
状态转移方程是什么?
- 问题拆分及找出最优子结构后,状态转移方程就很好推导了,存在两种情况
(1) 背包容量大于等于下一个物品的重量:物品存在选择与不选两种情况
(2) 背包容量小于下一个物品重量:物品不可被选择,情况只有一种
可得背包问题的状态转移方程为
func(n, c) = max(func(n - 1, c - W[n - 1]) + V[n - 1], func(n - 1, c)) (n > 1, c >= W[n - 1])
func(n, c) = func(n - 1, c) (n > 1, c < W[n - 1])
其中
n => 剩余物品数量
c => 背包剩余容量
W => 物品重量数组
V => 物品价值数组
边界是什么?
问题不断的向子问题拆分后一定会有一个头,如爬楼梯是将一阶和二阶楼梯作为边界,针对背包问题,它的边界是什么?
- 不难想到,当只剩最后一个物品,此时没有多余的物品能够选择了,就只能选择此物品,而选择此问题有两种情况
(1) 背包容量大于等于物品重量:此时返回物品价值
(2) 背包容量小于物品重量:此时返回0
可得背包问题的边界为
func(1, c) = V[0] (n = 1, c >= W[0])
func(1, c) = 0 (n = 1, c < W[0])
编码实现
简单递归
/**
* 获取最大价值
*
* @param n 物品数量
* @param c 背包剩余承重量
* @param w 物品重量
* @param v 物品价值
* @return 背包装配物品的最大价值
*/
int getMaxValues(int n, int c, int[] w, int[] v) {
if (n == 1) { // 边界
if (c >= w[0]) {
return v[0];
} else {
return 0;
}
}
if (c >= w[n - 1]) { // 状态转移公式
return Math.max(getMaxValues(n - 1, c - w[n - 1], w, v) + v[n - 1],
getMaxValues(n - 1, c, w, v));
} else {
return getMaxValues(n - 1, c, w, v);
}
}
备忘录算法
int getMaxValues(int n, int c, int[] w, int[] v) {
return getMaxValues(n, c, w, v, null);
}
int getMaxValues(int n, int c, int[] w, int[] v, Map<String, Integer> cache) {
if (n == 1) { // 边界
if (c >= w[0]) {
return v[0];
} else {
return 0;
}
}
if (cache == null) {
cache = new HashMap<>((int) Math.ceil(Math.log(n) / Math.log(2)));
}
if (cache.containsKey(generatorCacheKey(n, c))) {
return cache.get(generatorCacheKey(n, c));
}
int value;
if (c >= w[n - 1]) { // 状态转移公式
value = Math.max(getMaxValues(n - 1, c - w[n - 1], w, v, cache) + v[n - 1],
getMaxValues(n - 1, c, w, v, cache));
} else {
value = getMaxValues(n - 1, c, w, v, cache);
}
cache.put(generatorCacheKey(n, c), value);
return value;
}
String generatorCacheKey(int n, int c) {
return String.format("%s_%s", n, c);
}
动态规划算法
跟爬楼梯问题一样,我们自底向上来思考这个问题,我们不妨基于简化的问题画一个表格来分析这个情况,表格第一列表示5个物品的情况,括号内代表价值与重量,表格的第一行表示给予的背包容量,其余的空白格子代表背的最大价值数。
简化的问题:有5组物品,其中它的价值与重量分别为[4,2,1,3,1]、[4,3,2,1,2],背包可承受总重量为6。
剩余1容量 | 剩余2容量 | 剩余3容量 | 剩余4容量 | 剩余5容量 | 剩余6容量 | |
---|---|---|---|---|---|---|
物品1 (4,4) | ||||||
物品2 (2,3) | ||||||
物品3 (1,2) | ||||||
物品4 (3,1) | ||||||
物品5 (1,2) | ||||||
第一行非常容易填写,只有一个物品的情况下,背包最大价值要么为0要么为4,各自中箭头前面描述的是选择了那几个物品。
剩余1容量 | 剩余2容量 | 剩余3容量 | 剩余4容量 | 剩余5容量 | 剩余6容量 | |
---|---|---|---|---|---|---|
物品1 (4,4) | 0 | 0 | 0 | 1 => 4 | 1 => 4 | 1 => 4 |
物品2 (2,3) | ||||||
物品3 (1,2) | ||||||
物品4 (3,1) | ||||||
物品5 (1,2) | ||||||
我们将其余的格子全部填写完成,接下来的这几段很重要,理解它就理解了动态规划算法的核心。
物品(v,w)/c | 剩余1容量 | 剩余2容量 | 剩余3容量 | 剩余4容量 | 剩余5容量 | 剩余6容量 |
---|---|---|---|---|---|---|
物品1 (4,4) | 0 | 0 | 0 | 1 => 4 | 1 => 4 | 1 => 4 |
物品2 (2,3) | 0 | 0 | 2 => 2 | 1 => 4💧 | 1 => 4 | 1 => 4💧 |
物品3 (1,2) | 0 | 3 => 1 | 2 => 2 | 1 => 4🌙 | 1 => 4🌙 | 1,3 => 5🌀 |
物品4 (3,1) | 4 => 3 | 4 => 3 | 3,4 => 4 | 1,3 => 5 | 1,4 => 7⭐ | 1,4 => 7 |
物品5 (1,2) | 4 => 3 | 4 => 3 | 3,4 => 4 | 1,3 => 5 | 1,4 => 7 | 1,4 => 7 |
-
我们来找一下规律
-
先回顾一下核心的状态转移方程
func(n, c) = max(func(n - 1, c - W[n - 1]) + V[n - 1], func(n - 1, c))
-
我们先看🌀/💧这个图标组合,做一个方程代入
n = 3 , c = 6 , V[2] = 1 , W[2] = 2
注意,这里V[2]、W[2]对应的是物品3,因为数组从0开始编号
func(3, 6) = max(func(2, 4) + 1 , func(2, 6)) -
再看⭐/🌙这个图标组合,做一个方程代入
n = 4 , c = 5 , V[3] = 3 , W[3] = 1
func(4, 5) = max(func(3, 4) + 3 , func(3, 5))
-
规律已经很明显了,每个格子的数据都只依赖于它的前一行数据,和爬楼梯中我们最后只存储了前两步数据的思路一样,在这里我们只需要存储前一行的数据即可推导出下一行的数据,编码的思路和我们填充表格的思路一致,代码如下:
int getMaxValues(int n, int c, int[] w, int[] v) {
int[] pre = new int[c + 1]; // 前一行
int[] current = new int[c + 1]; // 当前行
for (int i = 1; i <= c; i++) { // 先填充第一行
if (i < w[0]) {
pre[i] = 0;
} else {
pre[i] = v[0];
}
}
for (int i = 1; i < n; i++) {
for (int j = 1; j <= c; j++) { // 填充第二行到最后
if (j < w[i]) { // 容量不够
current[j] = pre[j];
} else {
current[j] = Math.max(pre[j - w[i]] + v[i], pre[j]);
}
}
// 此处不可直接使用等号 会出现引用混乱的情况
pre = Arrays.copyOf(current, current.length);
}
return current[c];
}
题目扩展,采金矿
有一个国家发现了n座金矿,每座金矿的黄金储量(Vi)不同,需要参与挖掘的工人数(Li)也不同。参与挖矿工人的总数是C人。每座金矿要么全挖,要么不挖,不能派出一半人挖取一半金矿。要想得到尽可能多的黄金,应该选择挖取哪几座金矿?
此题是背包问题的变种,解题思路是一样的,有兴趣的同学可以自己思考一下。