题目描述
这是 LeetCode 上的 518. 零钱兑换 II ，难度为 中等。
Tag : 「背包问题」、「完全背包」、「动态规划」
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 1:
输入: amount = 5, coins = [1, 2, 5] 输出: 4 解释: 有四种方式可以凑成总金额: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1 复制代码
示例 2:
输入: amount = 3, coins = [2] 输出: 0 解释: 只用面额2的硬币不能凑成总金额3。 复制代码
示例 3:
输入: amount = 10, coins = [10] 输出: 1 复制代码
注意:
你可以假设：
- 0 <= amount (总金额) <= 5000
- 1 <= coin (硬币面额) <= 5000
- 硬币种类不超过 500 种
- 结果符合 32 位符号整数
完全背包（朴素解法）
在 322. 零钱兑换 中，我们求的是「取得特定价值所需要的最小物品个数」。
对于本题，我们求的是「取得特定价值的方案数量」。
求的东西不一样，但问题的本质没有发生改变，同样属于「组合优化」问题。
你可以这样来理解什么是组合优化问题：
被选物品之间不需要满足特定关系，只需要选择物品，以达到「全局最优」或者「特定状态」即可。
同时硬币相当于我们的物品，每种硬币可以选择「无限次」，很自然的想到「完全背包」。
这时候可以将「完全背包」的状态定义搬过来进行“微调”：
定义 f[i][j]f[i][j] 为考虑前 ii 件物品，凑成总和为 jj 的方案数量。
为了方便初始化，我们一般让 f[0][x]f[0][x] 代表不考虑任何物品的情况。
因此我们有显而易见的初始化条件：f[0][0] = 1f[0][0]=1，其余 f[0][x] = 0f[0][x]=0。
代表当没有任何硬币的时候，存在凑成总和为 0 的方案数量为 1；凑成其他总和的方案不存在。
当「状态定义」与「基本初始化」有了之后，我们不失一般性的考虑 f[i][j]f[i][j] 该如何转移。
对于第 ii 个硬币我们有两种决策方案：
- 不使用该硬币：
f[i - 1][j]f[i−1][j]
- 使用该硬币：由于每个硬币可以被选择多次（容量允许的情况下），因此方案数量应当是选择「任意个」该硬币的方案总和：
\sum_{k = 1}^{\left \lfloor {j / val} \right \rfloor}f[i - 1][j - k * val], val = nums[i - 1]k=1∑⌊j/val⌋f[i−1][j−k∗val],val=nums[i−1]
代码：
class Solution { public int change(int cnt, int[] cs) { int n = cs.length; int[][] f = new int[n + 1][cnt + 1]; f[0][0] = 1; 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++) { f[i][j] += f[i - 1][j - k * val]; } } } return f[n][cnt]; } } 复制代码
- 时间复杂度：共有 n * cntn∗cnt 个状态需要转移，每个状态转移最多遍历 cntcnt 次。整体复杂度为 O(n * cnt^2)O(n∗cnt2)。
- 空间复杂度：O(n * cnt)O(n∗cnt)。
完全背包（一维优化）
显然二维完全背包求解方案复杂度有点高。
nn 的数据范围为 10^2102，cntcnt 的数据范围为 10^3103，总的计算量为 10^8108 以上，处于超时边缘（实际测试可通过）。
我们需要对其进行「降维优化」，可以使用最开始讲的 数学分析方式，或者上一讲讲的 换元优化方式 进行降维优化。
由于 数学分析方式 十分耗时，我们用得更多的 换元优化方式。两者同样具有「可推广」特性。
因为后者更为常用，所以我们再来回顾一下如何进行「直接上手写一维空间优化的版本」 ：
- 在二维解法的基础上，直接取消「物品维度」
- 确保「容量维度」的遍历顺序为「从小到大」（适用于「完全背包」）
- 将形如 f[i - 1][j - k * val]f[i−1][j−k∗val] 的式子更替为 f[j - val]f[j−val]，同时解决「数组越界」问题（将物品维度的遍历修改为从 valval 开始）
代码：
class Solution { public int change(int cnt, int[] cs) { int n = cs.length; int[] f = new int[cnt + 1]; f[0] = 1; for (int i = 1; i <= n; i++) { int val = cs[i - 1]; for (int j = val; j <= cnt; j++) { f[j] += f[j - val]; } } return f[cnt]; } } 复制代码
- 时间复杂度：共有 n * cntn∗cnt 个状态需要转移，整体复杂度为 O(n * cnt)O(n∗cnt)。
- 空间复杂度：O(cnt)O(cnt)。
最后
这是我们「刷穿 LeetCode」系列文章的第 No.518 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
