聊聊算法:动态规划
前言
动态规划。这是一个有趣的话题,因为对于大部分业务型公司来说,面试中的算法部分并不会考这一块。但是BAT等一线互联网公司又不一定不会考,比如我在面试头条的时候就被问了一道动态规划的题目。
此外,我个人觉得动态规划有趣的原因是,我认为应用层的工程师能接触到或者用到的“最需要思考”的算法题目了。所以咱们今天就好好聊一聊动态规划。
正文
一、贪心算法
聊动态规划之前,我想先聊一聊贪心算法。
1.1、什么事贪心算法
一个很经典的题目:我们手里有1元、5元、10元、50元面值的若干纸币。我们需要用最少张数拿正好66元钱。我们应该怎么拿?
在这样的给定条件下,我们采用每次拿面值最大,直到凑够66元的策略:1张 * 50元 + 1张 * 10元 + 1张 * 5元 + 1张 * 1元。那么此时正巧达成题目中的答案。OK,这种策略我们都知道叫做:“贪心”。
1.2、贪心算法的弊端
贪心算法在一定条件下的确能够得出我们想要的结果。当然我们也很清楚,在一定条件下,贪心算法也并不能得到我们想要的结果。比如:在1元、5元、11元面值的前提下,拿最少张数凑出15元。
在贪心算法的策略下:1张 * 11元 + 4张 * 1元。但是3张 * 5元明显可以做到更优。
我们很清楚贪心算法的问题出在哪:贪心算法每次会都选择当前情况下的最优解。但是有时一味地只看重“眼前的利益”,并不一定会“笑到最后”。
贪心算法就是最真实的例子。
1.3、能否改进
既然我们明白贪心算法错就错在:每一步只考虑了当下最优解。那么换个角度来说,是不是只要我们每一步考虑全局最优解就能解决这个问题。
可是转念一想,每一步考虑全局最优解似乎不大可能。
的确我们想每一步都做到全局最优解的确是不可能。但我们可以换一种思路:我们可以去让未来告诉我们答案。
这种思想就是动态规划。
二、动态规划
2.1、暴力破解?
还是刚才那个题目:在1元、5元、11元面值的前提下,拿最少张数凑出15元。
对于我们来说,我们的任务就是:每一次从1元、5元、11元的钱币中拿出一张,最少在第几次拿完凑出了15元。
所以这个问题可以用一张图来表示:
image.png我们会发现,对于当前的我来说:我除了知道我还需要凑多少钱,以及我拿了几张钱币以外我什么都不清楚(既然如此,我还考虑个屁最优解!)。所以既然我们根本不能提前知道接下来会怎么样,那我们就把这个难题交给下一步...因为最后一步终究会凑出15元...
我猜小伙伴们读到这,已经开始骂娘了...tm的,我也明白可以这么做啊。不就是暴力破解吗!
2.2、非也
咱们来模拟一下,这里所谓的“暴力破解”:
- 情况1:假设第一步我拿了11元,我还需要4元,那么第二、第三、第四、第五步我只能依次拿1元。最终拿了5张。
- 情况2:假设第一步我拿了5元,我还需要10元,此时我没办法拿11元;所以第二步可以选择拿5元/1元,而第三步也是如此。最好的选择拿3张5元,最终拿了3张。
- 情况3:假设第一步我拿了1元,我还需要14元,那么此时摆在我面前的选择:可以拿11元,也可以拿5元,也可以拿1元。因此对于情况3,我们有更多的选择去尝试...假设你尝试完了所有选择,你会发现最终拿了5张。
此时,不知道大家发没发现一个现象:对于当下的我来说,当下已经不重要了,因此此时无论怎样我都会选择一张钱币。而真正有意义的操作意味未来我该怎么选。如果未来的我拿了最少的张数,那么对我当下的我来说选择哪个都不重要!
那么此时,如果我们用函数去表达情况3:定义一个f(n),表示凑n块钱最少需要拿几张。对于情况1来说,第一步的函数表达式:f(15) = min(f(15-11) , f(15-5) , f(15-1)) + 1
。
这里的含义:第一步我随便拿,我只需要保证我拿完之后,接下来拿的张数最少即可。也就是说我不考虑这一步我是拿了11元,还是5元,还是1元。我只关心我拿完之后接下来最少就好,也就是min(f(15-11) , f(15-5) , f(15-1))
->min(f(4) , f(10) , f(14))
。
而min(f(4) , f(10) , f(14))
又可以分别演化成:
- f(4) = min(f(4-1))
- f(10) = min(f(10-5) , f(10-1))
- f(14) = min(f(14-11) , f(14-5) , f(14-1))
所以我们只关心f(n),至于是f(n-11)还是f(n-5)还是f(n-1),我们统统不关心!
2.3、实现
我猜认真思考的小伙伴已经大概明白了这题的思路。这里贴一个有意思的反向解题代码,大家加深一下印象:
private lateinit var moneyRecord :IntArray // 这个数组的每个下标存储:凑足0-n面值的钱,最少使用拿几张
private val coins = intArrayOf(1, 5, 11) // 面值
fun funtion(curMoney: Int, allMoney: Int) { // curMoney:当前需要凑的面值,从0开始跌增到allMoney(最终需要凑的面值,也就是15)
if (curMoney == 0) {
moneyRecord[curMoney] = 0
funtion(curMoney + 1, allMoney)
} else {
var min = 9999999 // 初始化一个很大的数值。当最后如果得出的结果是这个数时,说明凑不出来。
// 在1、5、11面值中,最少次数能够凑齐curMoney面值
for (coin in coins) {
if (curMoney >= coin && moneyRecord[curMoney - coin] + 1 < min) {
min = moneyRecord[curMoney - coin] + 1
}
}
moneyRecord[curMoney] = min
// 递归
if (curMoney < allMoney) {
funtion(curMoney + 1, allMoney)
}
}
}
2.4、总结
动态规划与暴力破解的区别在哪里:
暴力破解明显的特征,我们需要考虑到所有的边界条件,这样带来的问题就是if特别的多。
而动态规划所有的边界条件就是一共有几种可能。对于动态规划来说,我们只关系结果,并不关心结果是怎么算出来的。譬如,求出f(15),只需要知道f(14),f(10),f(4)的值。其他信息并不需要。所以我们就可以将其简化和相同问题的递归。
也就是“学术界”为其总结的俩个性质:
- 无后效性
- 最优子结构
而这就是动态规划。
尾声
最近真的忙...忙的都想离职了。不爽!哈哈,但是生活还是要继续~~冲鸭!