【动态规划/背包问题】强化「换元一维优化」技巧

前言

今天是我们讲解「动态规划专题」中的 「背包问题」的第七天。

本篇我们继续完成与 完全背包 相关的练习题，共三篇。

本篇是第三篇，第一篇在 这里，第二篇在 这里。

另外，我在文章结尾处列举了我所整理的关于背包问题的相关题目。

背包问题我会按照编排好的顺序进行讲解（每隔几天更新一篇，确保大家消化）。

你也先可以尝试做做，也欢迎你向我留言补充，你觉得与背包相关的 DP 类型题目 ~

题目描述

这是 LeetCode 上的「518. 零钱兑换 II」，难度为 Medium。

给定不同面额的硬币和一个总金额。

写出函数来计算可以凑成总金额的硬币组合数。

假设每一种面额的硬币有无限个。

示例 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. 零钱兑换 中，我们求的是「取得特定价值所需要的最小物品个数」。

对于本题，我们求的是「取得特定价值的方案数量」。

求的东西不一样，但问题的本质没有发生改变，同样属于「组合优化」问题。

你可以这样来理解什么是「组合问题」：

被选物品之间不需要满足特定关系，只需要选择物品，以达到「全局最优」或者「特定状态」即可。

同时硬币相当于我们的物品，每种硬币可以选择「无限次」，很自然的想到「完全背包」。

这时候可以将「完全背包」的状态定义搬过来进行“微调”：

定义

为考虑前

件物品，凑成总和为

的方案数量。

为了方便初始化，我们一般让

代表不考虑任何物品的情况。

因此我们有显而易见的初始化条件：

，其余

。

代表当没有任何硬币的时候，存在凑成总和为 0 的方案数量为 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];
    }
}

• 时间复杂度：共有

个状态需要转移，每个状态转移最多遍历

次。整体复杂度为

。

• 空间复杂度：

。

完全背包（一维优化）

显然二维完全背包求解方案复杂度有点高。

的数据范围为

，

的数据范围为

，总的计算量为

以上，处于超时边缘（实际测试可通过）。

我们需要对其进行「降维优化」，可以使用最开始讲的 数学分析方式，或者上一讲讲的 换元优化方式 进行降维优化。

由于 数学分析方式 十分耗时，我们用得更多的 换元优化方式。两者同样具有「可推广」特性。

因为后者更为常用，所以我们再来回顾一下如何进行 换元一维优化 ：

1. 在二维解法的基础上，直接取消「物品维度」
2. 确保「容量维度」的遍历顺序为「从小到大」（适用于「完全背包」）
3. 将形如

的式子更替为

，同时解决「数组越界」问题（将物品维度的遍历修改为从

开始）

代码：

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];
    }
}

• 时间复杂度：共有

个状态需要转移，整体复杂度为

。

• 空间复杂度：

。

总结

「322. 零钱兑换」 和 本篇的「518. 零钱兑换 II」本质是一样的。

之所将两题分开成两篇【练习】，主要是为了加强大家对于「一维优化」的熟练度。

上来先写一个「二维朴素版」然后再进行「数学分析」推导这样的做法太慢了，不适合于比赛或者笔试情景。

我们应当做到：上手就能写出「一维优化」版本，但同时在脑中思考的是二维的递推逻辑 ~

背包问题（目录）

1. 01背包 : 背包问题 第一讲
   1. 【练习】01背包 : 背包问题 第二讲
   2. 【学习&练习】01背包 : 背包问题 第三讲
2. 完全背包 : 背包问题 第四讲
   1. 【练习】完全背包 : 背包问题 第五讲
   2. 【练习】完全背包 : 背包问题 第六讲
   3. 【练习】完全背包 : 本篇
3. 多重背包
   1. 【练习】多重背包
4. 多重背包（优化篇）
   1. 【练习】多重背包（优化篇）
   2. 【练习】多重背包（优化篇）
5. 混合背包
   1. 【练习】混合背包
6. 分组背包
   1. 【练习】分组背包
7. 多维背包
   1. 【练习】多维背包
8. 树形背包
   1. 【练习篇】树形背包
9. 背包求方案数
   1. 【练习】背包求方案数
10. 背包求具体方案
    1. 【练习】背包求具体方案
11. 泛化背包
    1. 【练习】泛化背包

最后

这是我们「刷穿 LeetCode」系列文章的第 No.518 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。