【动态规划/背包问题】站在更高的角度看待一般性的背包问题一维空间优化

前言

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

本篇我们继续完成与 完全背包 相关的练习题，共三篇。本篇是第二篇，第一篇在 这里。

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

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

你也先可以尝试做做，也欢迎你向我留言补充，你觉得与背包相关的 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 <= coins.length <= 12
• 1 <= coins[i] <=

- 1

• 0 <= amount <=

完全背包（朴素解法）

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

如果不能，那么从现在开始就要培养这样的习惯：

当看到题目是给定一些「物品」，让我们从中进行选择，以达到「最大价值」或者「特定价值」时，我们应该联想到「背包问题」。

这本质上其实是一个组合问题：被选物品之间不需要满足特定关系，只需要选择物品，以达到「全局最优」或者「特定状态」即可。

再根据物品的「选择次数限制」来判断是何种背包问题。

本题每种硬币可以被选择「无限次」，我们可以直接套用「完全背包」的状态定义进行微调：

定义

为考虑前

件物品，凑成总和为

所需要的最少硬币数量。

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

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

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

，其余

。

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

• 时间复杂度：共有

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

。

• 空间复杂度：

。

总结

本节，我们先是从朴素「完全背包」的角度分析并解决了问题。

而在考虑「一维优化」的时候，由于已经有前两节「数学推导优化思路」的基础，我们这次站在了「更高」的角度去看待一维优化。

从抽象「成本」&「价值」，结合「换元法」的角度去理解一维优化过程。

这可以大大节省我们分析推导的时间。

建议大家加强理解 ~

下一节练习篇，我们会继续强化这个过程

背包问题（目录）

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.322 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。

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

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

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