相信大部分人都对「动态规划」很恐惧,me too!!
每次学完动规都信誓旦旦感觉自己学好了,但是一遇到题目就不知所措,感觉自己学了个寂寞!!!
今天 (2022-04-22 16:59:44) 正式开始动态规划的整理总结,始终坚持认为,「一味的输入」远比「学会输出」效果差得多,所以我希望我自己可以坚持「不断的输出」。好了,进入今天的主要内容!
首先,动态规划问题的一般形式就是求最值。动态规划其实是运筹学的一种最优化方法,只不过在计算机问题上应用比较多,比如说让你求最长递增子序列呀,最小编辑距离呀等等
既然是要求最值,那么核心问题是什么呢?求解动态规划的核心问题是穷举。因为要求最值,肯定要把所有「可行解」穷举出来,然后在其中找到「最优解」
但是,如果只是无脑穷举,那么肯定效率极其低下!因为动态规划问题具有一些特殊的特点,可以让我们的穷举变得「聪明」一点
首先,我们来介绍动态规划的三个特点:
由于存在「重叠子问题」,所以我们可以通过「备忘录」或者「DP table」来优化穷举过程,避免不必要的计算
这里先给出本人研究出来的一个思维框架:明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义
按照上面的思维框架,可以套用下面的伪代码:
# 初始化 base case
dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1的所有取值:
for 状态2 in 状态2的所有取值:
for ...
dp[状态1][状态2][...] = 求最值(选择1,选择2...)
下面通过「斐波那契数列问题」和「凑零钱问题」来详解动态规划的基本原理。前者主要是让你明白什么是「重叠子问题」(斐波那契数列没有求最值,所以严格来说不是动态规划问题),后者主要举集中于如何「列出状态转移方程」
题目详情可见 斐波那契数
这个题目相信大家肯定都见过,算是道入门题。之所以放在这里详细分析,是为了可以更好的理解「重叠子问题」的概念
相信大家肯定都是有思路的,下面先使用迭代的思路去解决问题。不出意外是可以顺利通过所有测试用例且未超时!
xxxxxxxxxx
public int fib(int n) {
if (n == 0 || n == 1) return n;
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
现在我们尝试用递归的思路去解决该问题 (没有思路的小伙伴可以先去刷二叉树的题目,锻炼自己的递归思维)
xxxxxxxxxx
public int fib(int n) {
if (n == 0 || n == 1) return n;
return fib(n - 1) + fib(n - 2);
}
显然,也是顺利通过了所有的测试用例!但使用递归比迭代耗时长了很多,这是为什么呢?
我们先画出上述递归的递归树看看 (假定 n = 20)
可以看到其实我们的递归中存在很多的冗余计算,如图中标注出来的两个分支f(18)
和f(17)
。这也正是本文开头所说的「重叠子结构:当处理规模为
所以我们可以通过「备忘录」或者「DP table」来优化穷举过程,避免不必要的计算
具体思路:记录子结构的结果,当递归某一子结构时,判断该子结构是否已被计算过。如果已经被计算过,直接从记录中读取结果;否则才去执行该子结构
具体优化代码如下:
xxxxxxxxxx
private int[] emeo = new int[n + 1];
public int fib(int n) {
if (n == 0 || n == 1) return n;
// 备忘录中存在该子结构
if (emeo[n] != 0) return emeo[n];
// 备忘录中存在该子结构,记录该子结构的结果
emeo[n] = fib(n - 1) + fib(n - 2);
return emeo[n];
}
瞬间就快了很多,因为我们几乎把所有的冗余都去除了
至此,带备忘录的递归解法的效率已经和迭代的动态规划解法一样了。实际上,这种解法和常见的动态规划解法已经差不多了,只不过这种解法是「自顶向下」进行「递归」求解,我们更常见的动态规划代码是「自底向上」进行「递推」求解。而「自底向上」进行「递推」求解其实就是前文使用迭代的方法求解 -> 传送门
这里详细解释一下「自顶向下」和「自底向上」
f(20)
,向下逐渐分解规模,直到f(1)
和f(2)
这两个 base case,然后逐层返回答案f(1)
和f(2)
(base case) 开始往上推,直到推到我们想要的答案f(20)
注意:一般在递归中,记录子结构结果的数据结构叫「备忘录:emeo」;而在递推中,记录子结构结果的数据结构叫「DP table」
根据迭代求解的思路,很容易给出这个问题的「状态转移方程」:
何为「状态转移方程」,其实就是明确给出「当前状态」是如何从「之前状态」转移过来的方程
回到题目中,即f(n)
是从f(n-1)
和f(n-2)
转移 (相加) 过来的
最后的最后,给出一个空间上优化的思路:由于f(n)
只和f(n-1) && f(n-2)
相关,故可以只用两个变量来存储这两个状态,然后不断更新
xxxxxxxxxx
public int fib(int n) {
if (n == 0 || n == 1) return n;
int f0 = 0, f1 = 1;
int f = 0;
for (int i = 2; i <= n; i++) {
f = f0 + f1;
f0 = f1;
f1 = f;
}
return f;
}
题目详情可见 零钱兑换
这个问题主要是为了让大家更好的理解「最优子结构」的概念
抛出一个生活中的问题:三门课「语文,数学,英语」,求你考出的最高总成绩?
答案很简单,当然就是语文考最高,数学考最高,英语考最高,最后的总成绩必然最高,为💯!!现在是不是有点理解「最优子结构」是什么东东了!!!
我们的原问题是「最高总成绩」,原问题具有三个子结构「语文成绩,数学成绩,英语成绩」,这三个子结构互相独立,互不影响,所以上述问题符合「最优子结构」
但是,如果加一个条件:语文成绩和数学成绩会互相制约,数学分数高,语文分数就会降低,反之亦然。这样的话,显然你能考到的最高总成绩就达不到总分了,按刚才那个思路就会得到错误的结果。因为子问题并不独立,语文数学成绩无法同时最优,所以最优子结构被破坏
现在回到凑零钱的问题上
分析:原问题「用最少的硬币数凑出总金额为 11」,如果知道凑出 10 的最少硬币数,那么只需要在该数量上 +1 即可得到原问题的答案 (在 10 的基础上增加一枚 1 元硬币即可)!因为硬币的数量是没有限制的,所以子问题之间没有相互制约,是互相独立的
现在根据开头给出的思维框架深度分析:明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义
amount = 0
时,返回为 0amount
dp
函数,一般来说函数的参数就是状态转移中会变化的量,即:「状态」;函数的返回值就是题目要求我们计算的量就本题来说,状态只有一个,即「目标金额」,题目要求我们计算凑出目标金额所需的最少硬币数量。所以我们可以这样定义dp
函数dp(n)
表示,输入一个目标金额n
,返回凑出目标金额n
所需的最少硬币数量
根据上面的分析,我们可以很容易的写出完整代码:
xxxxxxxxxx
public int coinChange(int[] coins, int amount) {
return dp(coins, amount);
}
// 定义:输入目标金额 amount,返回所需最少硬币数
// 状态:目标金额 amout
// 选择:所有可选硬币集合 coins
private int dp(int[] coins, int amount) {
// base case
if (amount == 0) return 0;
if (amount < 0) return -1;
// 做选择
int res = Integer.MIN_VALUE;
for (int coin : coins) {
// 计算子问题的结果
int subProblem = dp(coins, amount - coin);
// 子问题无解
if (subProblem == -1) continue;
// 在子问题中选择最优解
res = Math.min(res, subProblem + 1);
}
return res == Integer.MIN_VALUE ? -1 : res;
}
根据上面的代码,很容易给出这个问题的「状态转移方程」:
至此,这个问题其实就解决了,但是此时还存在「重叠子问题」。比如当amount = 11, coins = {1, 2, 5}
时,画出其递归树,如下图所示:
递归算法的时间复杂度分析:子问题总数
子问题总数为递归树的节点个数,但算法会进行剪枝,剪枝的时机和题目给定的具体硬币面额有关,所以可以想象,这棵树生长的并不规则,确切算出树上有多少节点是比较困难的。对于这种情况,我们一般的做法是按照最坏的情况估算一个时间复杂度的上界
假设目标金额为n
,给定的硬币个数为k
,那么递归树最坏情况下高度为n
(全用面额为 1 的硬币),然后再假设这是一棵满k
叉树,则节点的总数在
接下来看每个子问题的复杂度,由于每次递归包含一个for
循环,复杂度为
xxxxxxxxxx
private int[] emeo;
public int coinChange(int[] coins, int amount) {
emeo = new int[amount + 1];
Arrays.fill(emeo, -666);
return dp(coins, amount);
}
private int dp(int[] coins, int amount) {
// base case
if (amount == 0) return 0;
if (amount < 0) return -1;
if (emeo[amount] != -666) return emeo[amount];
// 做选择
int res = Integer.MAX_VALUE;
for (int coin : coins) {
// 计算子问题的结果
int subProblem = dp(coins, amount - coin);
// 子问题无解
if (subProblem == -1) continue;
// 在子问题中选择最优解
res = Math.min(res, subProblem + 1);
}
emeo[amount] = res == Integer.MAX_VALUE ? -1 : res;
return emeo[amount];
}
在这里给出一版超时版本的答案
原因:当结果为 -1 时,emeo[amount]
没有更新
xxxxxxxxxx
private int dp(int[] coins, int amount) {
// base case
if (amount == 0) return 0;
if (amount < 0) return -1;
if (emeo[amount] != Integer.MAX_VALUE) return emeo[amount];
// 做选择
for (int coin : coins) {
// 计算子问题的结果
int subProblem = dp(coins, amount - coin);
// 子问题无解
if (subProblem == -1) continue;
// 在子问题中选择最优解
emeo[amount] = Math.min(emeo[amount], subProblem + 1);
}
return emeo[amount] == Integer.MAX_VALUE ? -1 : emeo[amount];
}
更改:
xxxxxxxxxx
// 其余逻辑不变!!
emeo[amount] = emeo[amount] == Integer.MAX_VALUE ? -1 : emeo[amount];
return emeo[amount];
当然,我们也可以自底向上使用 DP table 来消除重叠子问题,关于「状态」「选择」和 base case 与之前没有区别,dp
数组的定义和刚才dp
函数类似,也是把「状态」,也就是目标金额作为变量。不过dp
函数体现在函数参数,而dp
数组体现在数组索引:dp
数组的定义:当目标金额为i
时,至少需要dp[i]
枚硬币凑出
xxxxxxxxxx
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
// base case
dp[0] = 0;
for (int i = 1; i < dp.length; i++) {
for (int coin : coins) {
// 非法目标金额
if (i - coin < 0) continue;
dp[i] = Math.min(dp[i], dp[i - coin] + 1);
}
}
return dp[amount] == amount + 1 ? -1 : dp[amount];
}
注意:为什么不直接初始化为 int 型的最大值Integer.MAX_VALUE
呢?因为后面有dp[i - coin] + 1
,这就会导致整型溢出