一文搞定动态规划: 探索找零问题
这是寻找海蓝的第25篇原创文章
动态规划(Dynamic programming，简称DP)是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
从面试的角度看，动态规划是正规算法面试中无论如何都逃不掉的必考题,曾经有一个伟人说过这样一句话:
那么为什么动态规划会在面试中这么重要?
其实最主要的原因就是动态规划非常适合面试，因为动态规划没办法「背」。
我们很多求职者其实是通过背题来面试的，而之前这个做法屡试不爽，什么翻转二叉树、翻转链表，快排、归并、冒泡一顿背，基本上也能在面试中浑水摸鱼过去，其实这哪是考算法能力、算法思维，这就是考谁的备战态度好，愿意花时间去背题而已，把连背都懒得背的筛出去就完事了。
但是随着互联网遇冷，人才供给进一步过热，背题的人越来越多，面试的门槛被增加了，因此这个时候需要一种非常考验算法思维、变化多端而且容易设计的题目类型，动态规划就完美符合这个要求。
比如 LeetCode 中有1261道算法类题目,其中动态规划题目占据了近200道，动态规划能占据总题目的 1/6 的比例,可见其火热程度。
更重要的是，动态规划的题目难度以中高难度为主:
所以,既然我们已经知道这是算法面试的必考题了,我们怎么准备都不为过,我们准备花费7节的内容来详细讲解动态规划,尽笔者最大努力把动态规划讲清楚。
从「钱」讲起
我们在前面内容了解到了贪心算法可以解决「硬币找零问题」，但是那只是在部分情况下可以解决而已，因为题目中给出的钱币面值为 1、5、25，我们现实生活中我们现行的第五套人民币面值分别为100、50、20、10、5、1,我们的人民币是可以用贪心算法找零的。
那么有什么情况下不能用贪心算法吗？比如一个算法星球的央行发行了奇葩币，币值分别为1、5、11，要凑够15元，这个时候贪心算法就失效了。
我们可以算一下，按照贪心算法的策略，我们先拿出最大面值的11，剩下的4个分别对应四个1元的奇葩币，这总共需要五个奇葩币才能凑够15元。
而实际上我们简单一算，就知道最少情况是拿出3个五元的奇葩币才能凑够15元。
这里就有问题了,贪心算法的弊端在这种特殊面值钱币面前展露无疑,原因就在于「只顾眼前，无大局观」，在先拿出最大的 11 面值的奇葩币后就彻底把周旋余地堵死了,因为剩下的 4 要想凑足付出的代价是非常高的,我们需要依次拿出4个面值为1的奇葩币。
改进计算策略
那么既然贪心算法已经不适用于这种场景了,我们应该如何改变计算策略呢?
当我们面试过程中遇到这种问题时,如果一时没有思路,也要想到一种万能算法--暴力破解。
我们分析一下上述题目,它的问题其实是「给定一组面额的硬币,我们用现有的币值凑出n最少需要多少个币」。
我们要凑够这个 n,只要 n 不为0,那么总会有处在最后一个的硬币,这个硬币恰好凑成了 n,比如我们用 {11,1,1,1,1} 来凑15,前面我们拿出 {11,1,1,1},最后我们拿出 {1} 正好凑成 15。
如果用 {5,5,5} 来凑15,最后一个硬币就是5,我们按照这个思路捋一捋,：
那么假设最后一个硬币为11的话，那么剩下4，这个时候问题又变成了，我们凑出 n-11 最少需要多少个币,此时n=4，我们只能取出4个面值为1的币
如果假设最后一个硬币为 5 的话，这个时候问题又变成了，我们用现有的币值凑出 n-5 最少需要多少个币
大家发现了没有，我们的问题提可以不断被分解为「我们用现有的币值凑出 n 最少需要多少个币」,比如我们用 f(n) 函数代表 「凑出 n 最少需要多少个币」.
把「原有的大问题逐渐分解成类似的但是规模更小的子问题」这就是最优子结构,我们可以通过自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。
这个时候我们分别假设 1、5、11 三种面值的币分别为最后一个硬币的情况：
最后一枚硬币的面额为 11: min = f(4) + 1
最后一枚硬币的面额为 5: min = f(10) + 1
最后一枚硬币的面额为 1: min = f(14) + 1
这个时候大家发现问题所在了吗?最少找零 min 与 f(4)、f(10)、f(14) 三个函数解中的最小值是有关的，毕竟后面的「+1」是大家都有的。
假设凑的硬币总额为 n，那么 f(4) = f(n-11)、f(10) = f(n-5)、f(14) = f(n-1)，我们得出以下公式:
f(n) = min{f(n-1), f(n-5), f(n-11)} + 1
我们再具体到上面公式中 f(n-1) 凑够它的最小硬币数量是多少,是不是又变成下面这个公式:
f(n-1) = min{f(n-1-1), f(n-1-5), f(n-1-11)} + 1
以此类推…
这真是似曾相识,这不就是之前我们学习的递归吗?
是的,我们可以通过递归来求出最少找零问题的解,代码如下:
function f(n) {
if(n === 0) return 0
let min = Infinity
if (n >= 1) {
min = Math.min(f(n-1) + 1, min)
}
if (n >= 5) {
min = Math.min(f(n-5) + 1, min)
}
if (n >= 11) {
min = Math.min(f(n-11) + 1, min)
}
return min
}
console.log(f(15)) // 3
当n=0的时候,直接返回0,增加程序鲁棒性
我们先设最少找零 min 为 「无限大」，方便之后
Math.min求最小值当最后一个硬币为1的时候,我们递归
min = Math.min(f(n-1) + 1, min),求此种情况下的最小找零当最后一个硬币为5的时候,我们递归
min = Math.min(f(n-5) + 1, min),求此种情况下的最小找零当最后一个硬币为11的时候,我们递归
min = Math.min(f(n-11) + 1, min),求此种情况下的最小找零
递归的弊端
我们看似已经把问题解决了,但是别着急,我们继续测试,当n=70的时候,我们测试要凑出这个数最少我们需要多少个硬币。
答案是8,但是我们的耗时如下:
如果n=270呢?在八代i7处理器和node.js 12.x版本的加持下我跑了这么长时间都没算出来:
当n=27000的时候,我们成功的爆栈了:
所以为什么会造成如此长的执行耗时?归根到底是递归算法的低效导致的,我们看如下图:
我们如果计算f(70)就需要分别计算最后一个币为1、5、11三种面值时的不同情况，而这三种不同情况作为子问题又可以被分解为三种情况，依次类推…这样的算法复杂度有 O(3ⁿ),这是极为低效的。
我们再仔细看图:
我们用红色标出来的都是相同的计算函数，比如有两个f(64)、f(58)、f(54)，这些都是重复的,这些只是我们整个计算体系下的冰山一角,我们还有非常多的重复计算没办法在图中展示出来。
可见我们重复计算了非常多的无效函数，浪费了算力,到底有多浪费我们已经从上面函数执行时间测试上有了一定的认识。
我们不妨再举一个简单的例子，比如我们要计算 「1 + 1 + 1 + 1 + 1 + 1 + 1 + 1」的和。
我们开始数数…,直到我们数出上面计算的和为 8，那么，我们再在上述 「1 + 1 + 1 + 1 + 1 + 1 + 1 + 1」 后面 「+ 1」，那么和是多少？
这个时候你肯定数都不会数，脱口而出「9」。
为什么我们在后面的计算这么快？是因为我们已经在大脑中记住了之前的结果 「8」，我们只需要计算「8 + 1」即可，这避免了我们重复去计算前面的已经计算过的内容。
我们用的递归像什么？像继续数「1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1」来计算出「9」，这是非常耗时的。
我们假设用 m 种面值的硬币凑 n 最少需要多少硬币，在上述问题下递归的时间复杂度是惊人的O(nᵐ),指数级的时间复杂度可以说是最差的时间复杂度之一了。
我们已经发现问题所在了,大量的重复计算导致时间复杂度奇高,我们必须想办法解决这个问题。
备忘录与递归
既然已经知道存在大量冗余计算了,那么我们可不可以建立一个备忘录,把计算过的答案记录在备忘录中,再有我们需要答案的时候,我们去备忘录中查找,如果能查找到就直接返回答案,这样就避免了重复计算,这就是算法中典型的空间换时间的思维，我们用备忘录占用的额外内存换取了更高效的计算。
有了思路后,其实代码实现非常简单,我们只需要建立一个缓存备忘录,在函数内部校验校验是否存在在结果,如果存在返回即可。
function f(n) {
function makeChange(amount) {
if(amount <= 0) return 0
// 校验是否已经在备忘录中存在结果,如果存在返回即可
if(cache[amount]) return cache[amount]
let min = Infinity
if (amount >= 1) {
min = Math.min(makeChange(amount-1) + 1, min)
}
if (amount >= 5) {
min = Math.min(makeChange(amount-5) + 1, min)
}
if (amount >= 11) {
min = Math.min(makeChange(amount-11) + 1, min)
}
return (cache[amount] = min)
}
// 备忘录
const cache = []
return makeChange(n)
}
console.log(f(70)) // 8public class Cions {
public static void main(String[] args) {
int a = coinChange(70);
System.out.println(a);
}
private static HashMap<Integer,Integer> cache = new HashMap<>();
public static int coinChange(int amount) {
return makeChange(amount);
}
public static int makeChange(int amount) {
if (amount <= 0) return 0;
// 校验是否已经在备忘录中存在结果,如果存在返回即可
if(cache.get(amount) != null) return cache.get(amount);
int min = Integer.MAX_VALUE;
if (amount >= 1) {
min = Math.min(makeChange(amount-1) + 1, min);
}
if (amount >= 5) {
min = Math.min(makeChange(amount-5) + 1, min);
}
if (amount >= 11) {
min = Math.min(makeChange(amount-11) + 1, min);
}
cache.put(amount, min);
return min;
}
}我们的执行时间只有:
实际上利用备忘录来解决递归重复计算的问题叫做「记忆化搜索」。
这个方法本质上跟回溯法的「剪枝」是一个目的，就是把上图中存在重复的节点全部剔除,只保留一个节点即可,当然上图没办法把所有节点全部展示出来,如果剔除全部重复节点最后只会留下线性的节点形式:
这个带备忘录的递归算法时间复杂度只有O(n),已经跟动态规划的时间复杂度相差不大了。
那么这不就可以了吗？为什么还要搞动态规划？
还记得我们上面提到递归的另一大问题吗？
爆栈！
这是我们备忘录递归计算 f(27000) 的结果:
编程语言栈的深度是有限的,即使我们进行了剪枝,在五位数以上的情况下就会再次产生爆栈的情况,这导致递归根本无法完成大规模的计算任务。
这是递归的计算形式决定的,我们这里的递归是「自顶向下」的计算思路，即从 f(70) f(69)...f(1) 逐步分解,这个思路在这里并不完全适用,我们需要一种「自底向上」的思路来解决问题。
「自底向上」就是 f(1) ... f(70) f(69)通过小规模问题递推来解决大规模问题,动态规划通常是用迭代取代递归来解决问题。
「自顶向下」的思路在另一种算法思想中非常常见,那就是分治算法
除此之外,递归+备忘录的另一个缺陷就是再没有优化空间了,因为在最坏的情况下，递归的最大深度是 n。
因此，我们需要系统递归堆栈使用 O(n) 的空间,这是递归形式决定的,而换成迭代之后我们根本不需要如此多的的储存空间,我们可以继续往下看。
动态转移方程
还记得上面我们利用备忘录缓存之后各个节点的形式是什么样的吗,我们把它这个「备忘录」作为一张表，这张表就叫做 DP table,如下:
注意: 上图中
f[n]代表凑够 n 最少需要多少币的函数,方块内的数字代表函数的结果
我们不妨在上图中找找规律?
我们观察f[1]: f[1] = min(f[0], f[-5], f[-11]) + 1
由于f[-5] 这种负数是不存在的,我们都设为正无穷大,那么f[1] = 1。
再看看f[5]: f[1] = min(f[4], f[0], f[-6]) + 1,这实际是在求f[4] = 4、f[0] = 0、f[-6]=Infinity中最小的值即0，最后加上1，即1，那么f[5] = 1。
发现了吗？我们任何一个节点都可以通过之前的节点来推导出来，根本无需再做重复计算，这个相关的方程是:
f[n] = min(f[n-1], f[n-5], f[n-11]) + 1
还记得我们提到的动态规划有更大的优化空间吗?递归+备忘录由于递归深度的原因需要 O(n) 的空间复杂度,但是基于迭代的动态规划只需要常数级别的复杂度。
看下图,比如我们求解 f(70),只需要前面三个解,即 f(59) f(69) f(65) 套用公式即可求得,那么 f(0)f(1) ... f(58) 根本就没有用了,我们可以不再储存它们占用额外空间,这就留下了我们优化的空间。
上面的方程就是动态转移方程,而解决动态规划题目的钥匙也正是这个动态转移方程。
当然,如果你只推导出了动态转移方程基本上可以把动态规划题做出来了,但是往往很多人却做不对,这是为什么?这就得考虑边界问题。
边界问题
部分的边界问题其实我们在上面的部分已经给出解决方案了,针对这个找零问题我们有以下边界问题。
处理f[n]中n为负数的问题: 针对这个问题我们的解决方案是凡是n为负数的情况,一律将f[n]视为正无穷大,因为正常情况下我们是不会有下角标为负数的数组的,所以其实 n 为负数的 f[n] 根本就不存在,又因为我们要求最少找零,为了排除这种不存在的情况,也便于我们计算,我们直接将其视为正无穷大,可以最大程度方便我们的动态转移方程的实现。
处理f[n]中n为0的问题：n=0 的情况属于动态转移方程的初始条件,初始条件也就是动态转移方程无法处理的特殊情况,比如我们如果没有这个初始条件,我们的方程是这样的: f[0] = min(f[-1], f[-5], f[-11]) + 1,最小的也是正无穷大,这是特殊情况无法处理,因此我们只能人肉设置初始条件。
处理好边界问题我们就可以得到完整的动态转移方程了:
f[0] = 0 (n=0)
f[n] = min(f[n-1], f[n-5], f[n-11]) + 1 (n>0)
找零问题完整解析
那么我们再回到这个找零问题中,这次我们假设给出不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
比如:
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
其实上面的找零问题就是我们一直处理的找零问题的通用化,我们的面额是定死的,即1、5、11，这次是不定的，而是给了一个数组 coins 包含了相关的面值。
有了之前的经验,这种问题自然就不再话下了,我们再整理一下思路。
确定最优子结构: 最优子结构即原问题的解由子问题的最优解构成,我们假设最少需要k个硬币凑足总面额n,那么f(n) = min{f(n-cᵢ)}, cᵢ 即是硬币的面额。
处理边界问题: 依然是老套路,当n为负数的时候,值为正无穷大,当n=0时,值也为0.
得出动态转移方程:
f[0] = 0 (n=0)
f[n] = min(f[n-cᵢ]) + 1 (n>0)
我们根据上面的推导,得出以下代码:
const coinChange = (coins, amount) => {
// 初始化备忘录,用Infinity填满备忘录，Infinity说明该值不可以用硬币凑出来
const dp = new Array(amount + 1).fill(Infinity)
// 设置初始条件为 0
dp[0] = 0
for (var i = 1; i <= amount; i++) {
for (const coin of coins) {
// 根据动态转移方程求出最小值
if (coin <= i) {
dp[i] = Math.min(dp[i], dp[i - coin] + 1)
}
}
}
// 如果 `dp[amount] === Infinity`说明没有最优解返回-1,否则返回最优解
return dp[amount] === Infinity ? -1 : dp[amount]
}class Solution {
public int coinChange(int[] coins, int amount) {
// 初始化备忘录,用amount+1填满备忘录,amount+1 表示该值不可以用硬币凑出来
int[] dp = new int[amount + 1];
Arrays.fill(dp,amount+1);
// 设置初始条件为 0
dp[0]=0;
for (int coin : coins) {
for (int i = coin; i <= amount; i++) {
// 根据动态转移方程求出最小值
if(coin <= i) {
dp[i]=Math.min(dp[i],dp[i-coin]+1);
}
}
}
// 如果 `dp[amount] === amount+1`说明没有最优解返回-1,否则返回最优解
return dp[amount] == amount+1 ? -1 : dp[amount];
}
}小结
我们本节的学习经历了一下历程：
从之前学习的贪心算法入手来解决找零问题，发现贪心算法并不是在任何情况下都能找到最优解
我们决定换一种思路来解决存在的问题，我们最终发现了关键点,即「最优子结构」
借助上面的两个发现，我们用递归的方式解决了最少找零问题
但是经过算法复杂度分析和实际测试，我们发现递归的方法效率奇低，我们必须用一种方法来解决当前问题
我们用备忘录+递归的形式解决了时间复杂度问题,但是自顶向下的思路导致我们无法摆脱爆栈的阴霾,我们需要一种「自底向上」的全新思路
我们通过动态转移方程以迭代的方式高效地解出了此题
其实动态规划本质上就是被一再优化过的暴力破解,我们通过动态规划减少了大量的重叠子问题,此后我们讲到的所有动态规划题目的解题过程，都可以从暴力破解一步步优化到动态规划。
本节我们学习了动态规划到底是怎么来的，在此后的解题过程中我们如果没有思路可以在脑子里把这个过程再过一遍，但是我们之后的题解就不会再把整个过程走一遍了，而是直接用动态规划来解题。
可能你会问面试题这么多,到底哪一道应该用动态规划?如何判断?
其实最准确的办法就是看题目中的给定的问题，这个问题能不能被分解为子问题，再根据子问题的解是否可以得出原问题的解。
当然上面的方法虽然准确,但是需要一定的经验积累,我们可以用一个虽然不那么准确,但是足够简单粗暴的办法,如果题目满足以下条件之一,那么它大概率是动态规划题目:
求最大值，最小值
判断方案是否可行
统计方案个数
知乎：寻找海蓝
掘金：寻找海蓝96
好看你就
点点
我