先来看一个问题:
有一座高度是10阶的楼梯,从下往上走,每跨一步可以是一级或两级台阶。要求用程序求出一共一共有多少种走法。
比如,一步一阶,一共10步,这是一种走法。我们可以简写为1,1,1,1,1,1,1,1,1,1。
再比如,每次走两阶,共5步,这是另一种走法。可简写为2,2,2,2,2。
当然,除此之外,还有很多走法。
容易想到的是利用排列组合的思想,写一个多层嵌套循环遍历出所有可能性,每遍历出一个组合,让计数器加一。
但是这个方法属于暴力枚举,时间复杂度是指数级别的,因此我们想要寻求更高效的解法。
这就是我们的主角动态规划了。先来看看定义:动态规划英文名为Dynamic Programming. 是一种分阶段求解决策问题的数学思想。但它不止用于编程领域,也应用于管理学,经济学,生物学。
是不是听起来高大上但是你还是什么都听不懂啊?
直白点就是一句话:大事化小,小事化了。
拿上面的题目来说,假设只剩最后一步就到达第10阶,这时候会出现几种情况呢?
两种,因为一步走一阶或者两阶,第一种是从第九阶到第十阶,第二种是从第八阶到第十阶。
暂且不管从0到8阶的过程,也不管从0到9阶的过程,想要走到第10阶,一定是从第九阶或者是第八阶开始。
接下来的新问题是:如果已知从0—9阶有X种走法,从0—8阶有Y种走法,那么从0—10阶有多少种走法呢?
没错,就是两部分的总和X+Y。
也就是说:0—10阶走法之和 = 0—8阶走法之和 + 0—9阶走法之和。
方便表达,写为:F(10) = F(9) + F(8)。那么我们怎么求F(9) 和 F(8) 呢?
利用刚才的思路可以推出:F(9) = F(8) + F(7); F(8) = F(7) + F(6)。
惊不惊喜?意不意外?我们正在把一个复杂的问题分阶段进行简化,逐步简化成简单的问题。
而这就是动态规划的思想。
继续上面的问题,当只剩下一阶或者两阶的时候有多少种走法呢?分别是一种和两种。由此,我们归纳出一下公式:
F(1) = 1;
F(2) = 2;
F(n) = F(n-1) + F(n-2);(n>=3)
动态规划中包含三个重要的概念:【最优子结构】、【状态转移公式】、【边界】。
还是上面的例子,我们分析得出F(10) = F(9) + F(8)。 F(9) 和 F(8) 就是F(10) 的最优子结构。
当只有一阶或者两阶台阶时,我们可以直接得出结果,无需继续简化。我们称F(1)和F(2)是问题的【边界】。如果一个问题没有边界,将永远无法得到有限的结果。
F(n) = F(n-1) + F(n-2)是阶段与阶段之间的【状态转移方程】。这是动态规划的核心,决定了问题的每一个阶段和下一个阶段的关系。
(可把我厉害坏了,叉会腰)
叉完腰就会发现:完成的仅仅是动态规划的前半部分:问题建模。下面才是真正麻烦的部分:求解问题。
解法1:前面提到的,递归。既然已经归纳出F(n) = F(n-1) + F(n-2),又知道了递归的结束条件。可以直接用递归实现,代码如下:
int getClimbingWays(int n) {
if(n < 1) {
return 0;
}
if(n == 1) {
return 0;
}
if(n == 2) {
return 0;
}
return getClimbingWays(n - 1) + getClimbingWays(n - 2);
}
代码比较简单,不做解释。
这样来算确实可以计算出最终答案,氮素让我们来看看它的时间复杂度,首先,递归路径是这样的:要计算F(n),就要先计算F(n - 1) 和 F(n - 2),以此类推
看起来hin复杂吧,像一颗二叉树吧。
没错,它就是一颗二叉树,树的节点个数就是我们递归方法所需要计算的次数。不难看出,这颗树的高度是N-1,节点个数接近2(n-1),所以方法的时间复杂度可以近似的看作O(2n)。
这效率是极低的,想想有什么可以优化的。
想好没有?没想好就再看看上面的图片,或者直接看下图的相同颜色节点
你没看错,有些相同的参数被重复计算了,而且越往下走,重复的越多(自己往下画画看)
对于重复计算的情况,应该怎么避免呢?
其中一个方法就是用缓存,先创建一个哈希表,每次把不同参数的计算结果存入哈希,当遇到相同参数时,再直接从哈希 表中取出,就不用重复计算了。我们把这成为备忘录算法。代码如下:
int getClimbingWays(int n, HashMap<Integer,Integer> map) {
if(n < 1) {
return 0;
}
if(n == 1) {
return 0;
}
if(n == 2) {
return 0;
}
if(map.contains(n)) {
return map.get(n);
} else {
int value = getClimbingWays(n - 1) + getClimbingWays(n - 2);
map.put(n,value);
return value;
}
上面代码中,当每次需要计算F(n)时,会首先从map集合中寻找匹配元素。若map中存在,则直接返回结果,若map中不存在,就计算出结果,存入备忘录中。
从F(1)到F(n)一共有n个不同的输入,在哈希表中存了N-2个结果,所以时间可空间复杂度都是O(N)。
下面再来看空间上的优化。能不能把空间复杂度进一步减小呢?
| 台阶数 | 1 | 2 | 3 | 4| 5 | 6 |7 | 8 | 9 |
| --------- |-----: | :----: |
|走法数 |1 | 2|||||||||
就让我们用这一张表格阐述奥义:表格上所表示的是已经确定的对应台阶数的走法数。
| 台阶数 | 1 | 2 | 3 | 4| 5 | 6 |7 | 8 | 9 |
|:----: |:-----: | :----: |:----: |:-----: | :----: |:----: |:-----: | :----: |
|走法数 |1
| 2
|3||||||||
第一次迭代,台阶数等于3走法数量是3,介个结果是怎么来的呢?是F(1)和F(2)相加得来的,F(3)只依赖于F(1)和F(2)。
| 台阶数 | 1 | 2 | 3 | 4| 5 | 6 |7 | 8 | 9 |
|:----: |:-----: | :----: |:----: |:-----: | :----: |:----: |:-----: | :----: |
|走法数 |1 | 2
|3
|5|||||||
第二次迭代,台阶数为4时,走法数是5,这是F(2)和F(3)相加得来的,所以F(4)只依赖于F(2)和F(3)。
| 台阶数 | 1 | 2 | 3 | 4| 5 | 6 |7 | 8 | 9 |
|:----: |:-----: | :----: |:----: |:-----: | :----: |:----: |:-----: | :----: |
|走法数 |1 | 2|3
|5
|8||||||
同理,在后续迭代中,F(5)只依赖于F(3)和F(4),F(6)只依赖于F(4)和F(5)……
由此可见,每一次迭代过程中,只要保留之前的两个状态,就可以推导出新的状态。而不用像备忘录算法那般把全部子状态都记录下来。这才是真正的动态规划的实现
解法3:动态规划实现
int getClimbingWays(int n) {
if(n < 1) {
return 0;
}
if(n == 1) {
return 0;
}
if(n == 2) {
return 0;
}
int a = 1;
int b = 2;
int temp = 0;
for(int i = 3; i <= n; i++) {
temp = a + b;
a = b;
b = temp;
}
return temp;
}
程序从i = 3 开始迭代,知道 i = n 结束。每一次迭代,都会计算出多一级台阶的走法数。迭代过程只需要保留两个临时变量 a 和 b,为了便于理解,引入了temp变量,代表了当前迭代的结果值。
现在看起来hin简洁有木有?
再来看看时间空间复杂度。时间复杂度明显的是O(0),由于引入了三个临时变量,所以空间复杂度为O(1)。
这就是动态规划,利用简洁的自底向上的递推方式,实现了时间和空间上的最优化。
氮素,这只是动态规划领域最简单的一道题,因为它只有一个变化维度。
下面给出相对复杂的一道题。
题目:有一个国家发现了5座金矿,每座金矿的黄金储量不同,需要参与挖掘的工人数也不同。参与挖矿工人的总数是10人。每座金矿要么全挖,要么不挖,不能派出一半人挖取一半金矿。要求用程序求解出,要想得到尽可能多的黄金,应该选择挖取哪几座金矿?