【动态规划】不信看完你还不懂动态规划 冷不防 2022-08-29 09:57 247阅读 0赞 # 1.什么是动态规划? # 维基百科:动态规划(Dynamic programming,简称DP)是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 > **使用场景:**动态规划常常适用于有重叠子问题和最优子结构性质的问题。 > > dynamic programming is a m·· ethod for solving a complex problem by breaking it down into a collection of simpler subproblems. 简单来说,动态规划其实就是,给定一个问题,我们把它拆成一个个子问题,直到子问题可以直接解决,然后把子问题答案保存起来,以减少重复计算。再根据子问题答案反推,得出原问题解的一种方法。 动态规划最核心的思想,就在于拆分子问题,记住过往,减少重复计算。 一般这些子问题很相似,可以通过函数关系式递推出来。动态规划就致力于解决每个子问题一次,减少重复计算,比如\`斐波那契数列\`,就可以看做入门级的经典动态规划问题。 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzM3MTA3MDIy_size_16_color_FFFFFF_t_70][] # **2.动态规划3个核心点** # * 确定边界--退出条件 * 确定最优子结构--拆分子问题 * 状态转移方程--子问题合并方式,即子问题和原问题关系,将子问题结果合并得出最终答案 对于这个3点,后面会做一一解释,请看我道来。 # 3.从「钱」讲起 # 一个算法星球的央行发行了奇葩币,币值分别为1、5、11,要凑够15元最少要几个货币? 它的问题其实是「给定一组面额的硬币,我们用现有的币值凑出n最少需要多少个币」。 我们要凑够这个 n,只要 n 不为0,那么总会有处在最后一个的硬币,这个硬币恰好凑成了 n,比如我们用 \{11,1,1,1,1\} 来凑15,前面我们拿出 \{11,1,1,1\},最后我们拿出 \{1\} 正好凑成 15。 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzM3MTA3MDIy_size_16_color_FFFFFF_t_70 1][] 如果用 \{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 以此类推... 这真是似曾相识,这不就是递归吗?是的,我们可以通过递归来求出最少找零问题的解。 # 4.递归解法 # public static int coinChange(int n) { if (n <= 0) return 0; int min = Integer.MAX_VALUE; if (n >= 1) { min = Math.min(coinChange(n - 1) + 1, min); } if (n >= 5) { min = Math.min(coinChange(n - 5) + 1, min); } if (n >= 11) { min = Math.min(coinChange(n - 11) + 1, min); } return min; } * 当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越来越大时,执行时间几何数增长,而且最后还出现栈溢出的情况。所以为什么会造成如此长的执行耗时?归根到底是递归算法的低效导致的。 我们如果计算f(70)就需要分别计算最后一个币为1、5、11三种面值时的不同情况,而这三种不同情况作为子问题又可以被分解为三种情况,依次类推...这样的算法复杂度有 O(3ⁿ),这是极为低效的。 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzM3MTA3MDIy_size_16_color_FFFFFF_t_70 2][] 我们再仔细看图: ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzM3MTA3MDIy_size_16_color_FFFFFF_t_70 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ᵐ),指数级的时间复杂度可以说是最差的时间复杂度之一了。我们已经发现问题所在了,大量的重复计算导致时间复杂度奇高,我们必须想办法解决这个问题。 # 5.备忘录与递归 # 既然已经知道存在大量冗余计算了,那么我们可不可以建立一个备忘录,把计算过的答案记录在备忘录中,再有我们需要答案的时候,我们去备忘录中查找,如果能查找到就直接返回答案,这样就避免了重复计算,这就是算法中典型的空间换时间的思维。 有了思路后,其实代码实现非常简单,我们只需要建立一个缓存备忘录,在函数内部校验校验是否存在在结果,如果存在返回即可。 public 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; } } **实际上利用备忘录来解决递归重复计算的问题叫做「记忆化搜索」。** ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzM3MTA3MDIy_size_16_color_FFFFFF_t_70 4][]这个方法本质上跟回溯法的「剪枝」是一个目的,就是把上图中存在重复的节点全部剔除,只保留一个节点即可,当然上图没办法把所有节点全部展示出来,如果剔除全部重复节点最后只会留下线性的节点形式: ![20210801190434694.png][] 带备忘录的递归算法时间复杂度只有O(n),已经跟动态规划的时间复杂度相差不大了。 那么这不就可以了吗?为什么还要搞动态规划?还记得我们上面提到递归的另一大问题吗? 爆栈!编程语言栈的深度是有限的,即使我们进行了剪枝,在五位数以上的情况下就会再次产生爆栈的情况,这导致递归根本无法完成大规模的计算任务。 这是递归的计算形式决定的,我们这里的递归是「自顶向下」的计算思路,即从 f(70) f(69)...f(1) 逐步分解。「自顶向下」的思路在另一种算法思想中非常常见,那就是分治算法。 这个思路在这里并不完全适用,我们需要一种「自底向上」的思路来解决问题。「自底向上」就是 f(1) ... f(70) f(69)通过小规模问题递推来解决大规模问题,动态规划通常是用迭代取代递归来解决问题。 除此之外,递归+备忘录的另一个缺陷就是再没有优化空间了,因为在最坏的情况下,递归的最大深度是 n。因此,我们需要系统递归堆栈使用 O(n) 的空间,这是递归形式决定的,而换成迭代之后我们根本不需要如此多的的储存空间,我们可以继续往下看。 # 6.动态规划算法 # 还记得上面我们利用备忘录缓存之后各个节点的形式是什么样的吗,我们把它这个「备忘录」作为一张表,这张表就叫做 DP table,如下: ![2021080119061915.png][] 注意: 上图中 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) 根本就没有用了,我们可以不再储存它们占用额外空间,这就留下了我们优化的空间。 ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzM3MTA3MDIy_size_16_color_FFFFFF_t_70 5][] 上面的方程就是动态转移方程,而解决动态规划题目的钥匙也正是这个动态转移方程。 当然,如果你只推导出了动态转移方程基本上可以把动态规划题做出来了,但是往往很多人却做不对,这是为什么?这就得考虑边界问题。 **边界问题** 部分的边界问题其实我们在上面的部分已经给出解决方案了,针对这个找零问题我们有以下边界问题。 处理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) 我们根据上面的推导,得出以下代码: 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]; } # 7.小结 # 我们总结一下学习历程: 1. 经过分析,我们用递归的方式解决了最少找零问题 2. 但是经过算法复杂度分析和实际测试,我们发现递归的方法效率奇低,我们必须用一种方法来解决当前问题 3. 我们用备忘录+递归的形式解决了时间复杂度问题,但是自顶向下的思路导致我们无法摆脱爆栈的阴霾,我们需要一种「自底向上」的全新思路 4. 我们通过动态转移方程以迭代的方式高效地解出了此题 其实动态规划本质上就是被一再优化过的暴力破解,我们通过动态规划减少了大量的重叠子问题,此后我们讲到的所有动态规划题目的解题过程,都可以从暴力破解一步步优化到动态规划。 可能你会问面试题这么多,到底哪一道应该用动态规划?如何判断? 其实最准确的办法就是看题目中的给定的问题,这个问题能不能被分解为子问题,再根据子问题的解是否可以得出原问题的解。 当然上面的方法虽然准确,但是需要一定的经验积累,我们可以用一个虽然不那么准确,但是足够简单粗暴的办法,如果题目满足以下条件之一,那么它大概率是动态规划题目: * 求最大值,最小值 * 判断方案是否可行 * 统计方案个数 **参考文档:** [看一遍就理解:动态规划详解][Link 1] [一文搞懂动态规划][Link 2] [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzM3MTA3MDIy_size_16_color_FFFFFF_t_70]: /images/20220829/4bc514b7602a486cb50c7902998cdf88.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzM3MTA3MDIy_size_16_color_FFFFFF_t_70 1]: /images/20220829/721f5ab7f17343c6a5d96bc08ca46e24.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzM3MTA3MDIy_size_16_color_FFFFFF_t_70 2]: /images/20220829/fab661b9101f45178e0480ce79cb9147.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzM3MTA3MDIy_size_16_color_FFFFFF_t_70 3]: /images/20220829/efccd46e5b5640288daf32f9ca400f00.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzM3MTA3MDIy_size_16_color_FFFFFF_t_70 4]: /images/20220829/8c40df933c944af5a5053fc9d9d235c5.png [20210801190434694.png]: /images/20220829/1e61d6b6bc46499ca6414fcf1ed79556.png [2021080119061915.png]: /images/20220829/e4ebc2f1b46a4802894de5a9a94587ae.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWR1XzM3MTA3MDIy_size_16_color_FFFFFF_t_70 5]: /images/20220829/069ac4401b164066baac9e815a801311.png [Link 1]: https://juejin.cn/post/6951922898638471181 [Link 2]: https://juejin.cn/post/6844904113889624077#heading-7
相关 动态规划 -------------------- 动态规划的设计思想 动态规划(DP)\[1\]通过分解成子问题解决了给定复杂的问题,并存储子问题的结果,以避免再次计算相同的结 柔情只为你懂/ 2022年09月25日 11:15/ 0 赞/ 195 阅读
相关 【动态规划】不信看完你还不懂动态规划 1.什么是动态规划? 维基百科:动态规划(Dynamic programming,简称DP)是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 > 使用 冷不防/ 2022年08月29日 09:57/ 0 赞/ 248 阅读
相关 动态规划 首先是概念:动态规划就是将原问题划分为简单的几个小问题(有点类似与分治法?但是分治法中的各个小问题是相互独立的,彼此之间不会产生影响,但是动态规划中所得的值和前面相关,当前的解 青旅半醒/ 2022年07月12日 05:01/ 0 赞/ 263 阅读
相关 动态规划 > 给定两个字符串A和B,返回两个字符串的最长公共子序列的长度。例如,A=”1A2C3D4B56”,B=”B1D23CA45B6A”,”123456”或者”12C4B6”都是最 以你之姓@/ 2022年06月07日 00:41/ 0 赞/ 253 阅读
相关 动态规划 基本思想: 动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。 区别: 与 ゞ 浴缸里的玫瑰/ 2022年05月25日 09:44/ 0 赞/ 382 阅读
相关 动态规划 一 动态规划 动态规划问题是面试题中的热门话题,如果要求一个问题的最优解(通常是最大值或者最小值),而且该问题能够分解成若干个子问题,并且小问题之间也存在重叠的子问题,则 矫情吗;*/ 2022年05月24日 23:23/ 0 赞/ 243 阅读
相关 动态规划 等我有时间了,一定要把《算法导论》啃完,这本书的印刷质量实在太好了,就是烧脑子,滑稽。 适合应用动态规划求解的最优化问题应该具备两个要素: 最优子结构:一个问题的最优解包含 短命女/ 2022年05月17日 09:45/ 0 赞/ 255 阅读
相关 动态规划 1.题目:最长递增子序列(Longest Increasing Subsequence) 问题描述: > 给定长度为N的数组A,计算A的最长单调递增的子序列(不一定连续) 妖狐艹你老母/ 2022年05月11日 04:56/ 0 赞/ 224 阅读
相关 动态规划 [https://blog.csdn.net/mmc2015/article/details/73558346][https_blog.csdn.net_mmc2015_art 淩亂°似流年/ 2022年05月09日 05:18/ 0 赞/ 256 阅读
相关 动态规划 算法题中动态规划是真的难,写一篇总结,彻底解决动态规划。参考:[https://blog.csdn.net/u013309870/article/details/7519359 左手的ㄟ右手/ 2021年11月19日 14:14/ 0 赞/ 422 阅读
还没有评论,来说两句吧...