今天是我们讲解「动态规划专题」中的 「背包问题」的第六天。
本篇我们继续完成与 完全背包 相关的练习题,共三篇。本篇是第二篇,第一篇在 这里。
另外,我在文章结尾处列举了我所整理的关于背包问题的相关题目。
背包问题我会按照编排好的顺序进行讲解(每隔几天更新一篇,确保大家消化)。
你也先可以尝试做做,也欢迎你向我留言补充,你觉得与背包相关的 DP 类型题目 ~
这是 LeetCode 上的「322. 零钱兑换」,难度为 Medium。
给定不同面额的硬币 coins 和一个总金额 amount。
编写一个函数来计算可以凑成总金额所需的最少的硬币个数。
如果没有任何一种硬币组合能组成总金额,返回 -1。
你可以认为每种硬币的数量是无限的。
示例 1:
输入:coins = [1, 2, 5], amount = 11
输出:3
解释:11 = 5 + 5 + 1
示例 2:
输入:coins = [2], amount = 3
输出:-1
示例 3:
输入:coins = [1], amount = 0
输出:0
示例 4:
输入:coins = [1], amount = 1
输出:1
示例 5:
输入:coins = [1], amount = 2
输出:2
提示:
- 1
硬币相当于我们的物品,每种硬币可以选择「无限次」,我们应该很自然的想到「完全背包」。
如果不能,那么从现在开始就要培养这样的习惯:
当看到题目是给定一些「物品」,让我们从中进行选择,以达到「最大价值」或者「特定价值」时,我们应该联想到「背包问题」。
这本质上其实是一个组合问题:被选物品之间不需要满足特定关系,只需要选择物品,以达到「全局最优」或者「特定状态」即可。
再根据物品的「选择次数限制」来判断是何种背包问题。
本题每种硬币可以被选择「无限次」,我们可以直接套用「完全背包」的状态定义进行微调:
定义
为考虑前
件物品,凑成总和为
所需要的最少硬币数量。
为了方便初始化,我们一般让
代表不考虑任何物品的情况。
因此我们有显而易见的初始化条件:
,其余
。
代表当没有任何硬币的时候,存在凑成总和为 0 的方案,方案所使用的硬币为 0;凑成其他总和的方案不存在。
由于我们要求的是「最少」硬币数量,因此我们不希望「无效值」参与转移,可设
。
当「状态定义」与「基本初始化」有了之后,我们不失一般性的考虑
该如何转移。
对于第
个硬币我们有两种决策方案:
代码:
class Solution {
int INF = Integer.MAX_VALUE;
public int coinChange(int[] cs, int cnt) {
int n = cs.length;
int[][] f = new int[n + 1][cnt + 1];
// 初始化(没有任何硬币的情况):只有 f[0][0] = 0;其余情况均为无效值。
// 这是由「状态定义」决定的,当不考虑任何硬币的时候,只能凑出总和为 0 的方案,所使用的硬币数量为 0
for (int i = 1; i <= cnt; i++) f[0][i] = INF;
// 有硬币的情况
for (int i = 1; i <= n; i++) {
int val = cs[i - 1];
for (int j = 0; j <= cnt; j++) {
// 不考虑当前硬币的情况
f[i][j] = f[i - 1][j];
// 考虑当前硬币的情况(可选当前硬币个数基于当前容量大小)
for (int k = 1; k * val <= j; k++) {
if (f[i - 1][j - k * val] != INF) {
f[i][j] = Math.min(f[i][j], f[i-1][j-k*val] + k);
}
}
}
}
return f[n][cnt] == INF ? -1 : f[n][cnt];
}
}
个状态需要转移,每个状态转移最多遍历
次。整体复杂度为
。
。
借这个问题,刚好说一下,我们初始化时,对于无效状态应该如何定义。
可以看到上述解法,将 INF
定义为 INT_MAX
。
这是因为我们转移时取的是较小值,我们希望无效值不要被转移,所以将 INF
定义为较大的数,以代表数学上的
(正无穷)。
这很合理,但是我们需要注意,如果我们在 INF
的基础上进行累加的话,常规的语言会将其变成负数最小值。
也就是在正无穷基础上进行累加,会丢失其正无穷的含义,这与数学上的正无穷概念冲突。
因此,我们才有先判断再使用的习惯:
if (f[i-1][j] != INF) {
f[i][j] = Math.min(f[i][j], f[i-1][j]);
}
但事实上,如果每次使用都需要有前置检查的话,是很麻烦的。
于是我们有另外一个技巧,不直接使用 INT_MAX
作为 INF
,而是使用一个比 INT_MAX
小的较大数来代表 INF
。
相当于预留了一些「累加空间」给 INF
。
比如使用 0x3f3f3f3f 作为最大值,这样我们使用 INF
做状态转移的时候,就不需要先判断再使用了。
代码:
class Solution {
int INF = 0x3f3f3f3f;
public int coinChange(int[] cs, int cnt) {
int n = cs.length;
int[][] f = new int[n + 1][cnt + 1];
for (int i = 1; i <= cnt; i++) f[0][i] = INF;
for (int i = 1; i <= n; i++) {
int val = cs[i - 1];
for (int j = 0; j <= cnt; j++) {
f[i][j] = f[i-1][j];
for (int k = 0; k * val <= j; k++) {
f[i][j] = Math.min(f[i][j], f[i-1][j-k*val] + k);
}
}
}
return f[n][cnt] == INF ? -1 : f[n][cnt];
}
}
显然朴素版的完全背包进行求解复杂度有点高。
在「学习完全背包」和「上一讲练习」中,我们从最朴素背包转移方程出发,从数学的角度去推导一维优化是如何来的。
这十分科学,而绝对严谨。
但每次都这样推导是十分耗时的。
因此,我们这次站在一个「更高」的角度去看「完全背包」问题。
我们知道传统的「完全背包」二维状态转移方程是:
经过一维空间优化后的状态转移方程是(同时容量维度遍历顺序为「从小到大」):
这是我们在 学习完全背包 时推导的,是经过严格证明的,具有一般性的。
然后我们只需要对「成本」&「价值」进行抽象,并结合「换元法」即可得到任意背包问题的一维优化状态转移方程。
拿我们本题的状态转移方程来分析,本题的朴素状态转移方程为:
我们将硬币的面值抽象为「成本」,硬币的数量抽象「价值」,再对物品维度进行消除,即可得:
如果还不理解,可以将上述四个状态转移方程「两两成对」结合来看。
代码:
class Solution {
int INF = 0x3f3f3f3f;
public int coinChange(int[] cs, int cnt) {
int n = cs.length;
int[] f = new int[cnt + 1];
for (int i = 1; i <= cnt; i++) f[i] = INF;
for (int i = 1; i <= n; i++) {
int val = cs[i - 1];
for (int j = val; j <= cnt; j++) {
f[j] = Math.min(f[j], f[j - val] + 1);
}
}
return f[cnt] == INF ? -1 : f[cnt];
}
}
个状态需要转移,整体复杂度为
。
。
本节,我们先是从朴素「完全背包」的角度分析并解决了问题。
而在考虑「一维优化」的时候,由于已经有前两节「数学推导优化思路」的基础,我们这次站在了「更高」的角度去看待一维优化。
从抽象「成本」&「价值」,结合「换元法」的角度去理解一维优化过程。
这可以大大节省我们分析推导的时间。
建议大家加强理解 ~
下一节练习篇,我们会继续强化这个过程
这是我们「刷穿 LeetCode」系列文章的第 No.322
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先将所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。