动态规划解题套路框架

509. 斐波那契数

322. 零钱兑换

 

相信大部分人都对「动态规划」很恐惧,me too!!

每次学完动规都信誓旦旦感觉自己学好了,但是一遇到题目就不知所措,感觉自己学了个寂寞!!!

今天 (2022-04-22 16:59:44) 正式开始动态规划的整理总结,始终坚持认为,「一味的输入」远比「学会输出」效果差得多,所以我希望我自己可以坚持「不断的输出」。好了,进入今天的主要内容!

 

首先,动态规划问题的一般形式就是求最值。动态规划其实是运筹学的一种最优化方法,只不过在计算机问题上应用比较多,比如说让你求最长递增子序列呀,最小编辑距离呀等等

既然是要求最值,那么核心问题是什么呢?求解动态规划的核心问题是穷举。因为要求最值,肯定要把所有「可行解」穷举出来,然后在其中找到「最优解」

但是,如果只是无脑穷举,那么肯定效率极其低下!因为动态规划问题具有一些特殊的特点,可以让我们的穷举变得「聪明」一点

首先,我们来介绍动态规划的三个特点:

由于存在「重叠子问题」,所以我们可以通过「备忘录」或者「DP table」来优化穷举过程,避免不必要的计算

这里先给出本人研究出来的一个思维框架:明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义

按照上面的思维框架,可以套用下面的伪代码:

下面通过「斐波那契数列问题」和「凑零钱问题」来详解动态规划的基本原理。前者主要是让你明白什么是「重叠子问题」(斐波那契数列没有求最值,所以严格来说不是动态规划问题),后者主要举集中于如何「列出状态转移方程」

斐波那契数列

题目详情可见 斐波那契数

这个题目相信大家肯定都见过,算是道入门题。之所以放在这里详细分析,是为了可以更好的理解「重叠子问题」的概念

相信大家肯定都是有思路的,下面先使用迭代的思路去解决问题。不出意外是可以顺利通过所有测试用例且未超时!

现在我们尝试用递归的思路去解决该问题 (没有思路的小伙伴可以先去刷二叉树的题目,锻炼自己的递归思维)

显然,也是顺利通过了所有的测试用例!但使用递归比迭代耗时长了很多,这是为什么呢?

我们先画出上述递归的递归树看看 (假定 n = 20)

1

可以看到其实我们的递归中存在很多的冗余计算,如图中标注出来的两个分支f(18)f(17)。这也正是本文开头所说的「重叠子结构:当处理规模为 n 的问题时,中间可能需要处理多个相同且规模为 ni 的问题」

所以我们可以通过「备忘录」或者「DP table」来优化穷举过程,避免不必要的计算

具体思路:记录子结构的结果,当递归某一子结构时,判断该子结构是否已被计算过。如果已经被计算过,直接从记录中读取结果;否则才去执行该子结构

具体优化代码如下:

瞬间就快了很多,因为我们几乎把所有的冗余都去除了

至此,带备忘录的递归解法的效率已经和迭代的动态规划解法一样了。实际上,这种解法和常见的动态规划解法已经差不多了,只不过这种解法是「自顶向下」进行「递归」求解,我们更常见的动态规划代码是「自底向上」进行「递推」求解。而「自底向上」进行「递推」求解其实就是前文使用迭代的方法求解 -> 传送门

这里详细解释一下「自顶向下」和「自底向上」

image-20220226164025008 注意:一般在递归中,记录子结构结果的数据结构叫「备忘录:emeo」;而在递推中,记录子结构结果的数据结构叫「DP table」

根据迭代求解的思路,很容易给出这个问题的「状态转移方程」

f(n)={n,n=0,1f(n1)+f(n2),n>1

何为「状态转移方程」,其实就是明确给出「当前状态」是如何从「之前状态」转移过来的方程

回到题目中,即f(n)是从f(n-1)f(n-2)转移 (相加) 过来的

最后的最后,给出一个空间上优化的思路:由于f(n)只和f(n-1) && f(n-2)相关,故可以只用两个变量来存储这两个状态,然后不断更新

凑零钱问题

题目详情可见 零钱兑换

这个问题主要是为了让大家更好的理解「最优子结构」的概念

抛出一个生活中的问题:三门课「语文,数学,英语」,求你考出的最高总成绩?

答案很简单,当然就是语文考最高,数学考最高,英语考最高,最后的总成绩必然最高,为💯!!现在是不是有点理解「最优子结构」是什么东东了!!!

我们的原问题是「最高总成绩」,原问题具有三个子结构「语文成绩,数学成绩,英语成绩」,这三个子结构互相独立,互不影响,所以上述问题符合「最优子结构」

但是,如果加一个条件:语文成绩和数学成绩会互相制约,数学分数高,语文分数就会降低,反之亦然。这样的话,显然你能考到的最高总成绩就达不到总分了,按刚才那个思路就会得到错误的结果。因为子问题并不独立,语文数学成绩无法同时最优,所以最优子结构被破坏

 

现在回到凑零钱的问题上

分析:原问题「用最少的硬币数凑出总金额为 11」,如果知道凑出 10 的最少硬币数,那么只需要在该数量上 +1 即可得到原问题的答案 (在 10 的基础上增加一枚 1 元硬币即可)!因为硬币的数量是没有限制的,所以子问题之间没有相互制约,是互相独立的

现在根据开头给出的思维框架深度分析:明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义

就本题来说,状态只有一个,即「目标金额」,题目要求我们计算凑出目标金额所需的最少硬币数量。所以我们可以这样定义dp函数dp(n)表示,输入一个目标金额n,返回凑出目标金额n所需的最少硬币数量

根据上面的分析,我们可以很容易的写出完整代码:

根据上面的代码,很容易给出这个问题的「状态转移方程」

dp(amount)={0,amount=01,amount=1min{dp(amountcoin)+1 | coincoins},amount>0

至此,这个问题其实就解决了,但是此时还存在「重叠子问题」。比如当amount = 11, coins = {1, 2, 5}时,画出其递归树,如下图所示:

2

递归算法的时间复杂度分析:子问题总数 × 解决每个子问题所需的时间

子问题总数为递归树的节点个数,但算法会进行剪枝,剪枝的时机和题目给定的具体硬币面额有关,所以可以想象,这棵树生长的并不规则,确切算出树上有多少节点是比较困难的。对于这种情况,我们一般的做法是按照最坏的情况估算一个时间复杂度的上界

假设目标金额为n,给定的硬币个数为k,那么递归树最坏情况下高度为n (全用面额为 1 的硬币),然后再假设这是一棵满k叉树,则节点的总数在 O(kn) 这个数量级

接下来看每个子问题的复杂度,由于每次递归包含一个for循环,复杂度为 O(k),相乘得到总时间复杂度为 O(kn),指数级别

优化一:带备忘录的递归

在这里给出一版超时版本的答案

原因:当结果为 -1 时,emeo[amount]没有更新

更改:

优化二:带 DP 的递推

当然,我们也可以自底向上使用 DP table 来消除重叠子问题,关于「状态」「选择」和 base case 与之前没有区别,dp数组的定义和刚才dp函数类似,也是把「状态」,也就是目标金额作为变量。不过dp函数体现在函数参数,而dp数组体现在数组索引:dp数组的定义:当目标金额为i时,至少需要dp[i]枚硬币凑出

image-20220226164025008 注意:为什么不直接初始化为 int 型的最大值Integer.MAX_VALUE呢?因为后面有dp[i - coin] + 1,这就会导致整型溢出