前言 动态规划。这是一个有趣的话题，因为对于大部分业务型公司来说，面试中的算法部分并不会考这一块。但是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元。
所以这个问题可以用一张图来表示：
文章图片
我们会发现，对于当前的我来说：我除了知道我还需要凑多少钱，以及我拿了几张钱币以外我什么都不清楚（既然如此，我还考虑个屁最优解！）。所以既然我们根本不能提前知道接下来会怎么样，那我们就把这个难题交给下一步…因为最后一步终究会凑出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))
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)的值。其他信息并不需要。所以我们就可以将其简化和相同问题的递归。
也就是“学术界”为其总结的俩个性质：
- 无后效性
- 最优子结构
尾声 最近真的忙…忙的都想离职了。不爽！哈哈，但是生活还是要继续~~冲鸭！
我是一个应届生，最近和朋友们维护了一个公众号，内容是我们在从应届生过渡到开发这一路所踩过的坑，以及我们一步步学习的记录，如果感兴趣的朋友可以关注一下，一同加油~ 【动态规划，凑硬币】
文章图片
