LC 322. 零钱兑换

题目描述

这是 LeetCode 上的 322. 零钱兑换 ，难度为 中等。

给定不同面额的硬币 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] <= $2^{31}$ - 1
• 0 <= amount <= $10^4$

---

完全背包（朴素解法）

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

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

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

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

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

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

定义 $f[i][j]$ 为考虑前 $i$ 件物品，凑成总和为 $j$ 所需要的最少硬币数量。

为了方便初始化，我们一般让 $f[0][x]$ 代表不考虑任何物品的情况。

因此我们有显而易见的初始化条件：$f[0][0] = 0$，其余 $f[0][x] = INF$。

代表当没有任何硬币的时候，存在凑成总和为 0 的方案，方案所使用的硬币为 0；凑成其他总和的方案不存在。

由于我们要求的是「最少」硬币数量，因此我们不希望「无效值」参与转移，因此可设 $INF = INT_MAX$。

当「状态定义」与「基本初始化」有了之后，我们不失一般性的考虑 $f[i][j]$ 该如何转移。

对于第 $i$ 个硬币我们有两种决策方案：

• 不使用该硬币：

  $$f[i - 1][j]$$

• 使用该硬币，由于每个硬币可以被选择多次（容量允许的情况下），因此最优解应当是所有方案中的最小值：

  $$min(f[i-1][j-k*coin] + k)$$

代码：

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

• 时间复杂度：共有 $n cnt$ 个状态需要转移，每个状态转移最多遍历 $cnt$ 次。整体复杂度为 $O(n cnt^2)$。
• 空间复杂度：$O(n * cnt)$。

---

无效状态的定义问题

借这个问题，刚好说一下，我们初始化时，对于无效状态应该如何定义。

可以看到上述解法，将 INF 定义为 INT_MAX。

这是因为我们转移时取的是较小值，我们希望无效值不要被转移，所以将 INF 定义为较大的数，以代表数学上的 $+\infty$ （正无穷）。

这很合理，但是我们需要注意，如果我们在 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];
    }
}

---

完全背包（一维优化）

显然朴素版的完全背包进行求解复杂度有点高。

在「学习完全背包」和「上一讲练习」中，我们从最朴素背包转移方程出发，从数学的角度去推导一维优化是如何来的。

这十分科学，而绝对严谨。

但每次都这样推导是十分耗时的。

因此，我们这次站在一个「更高」的角度去看「完全背包」问题。

我们知道传统的「完全背包」二维状态转移方程是：

$$f[i][j] = max(f[i - 1][j], f[i - 1][j - k * w[i]] + k* v[i])$$

经过一维空间优化后的状态转移方程是（同时容量维度遍历顺序为「从小到大」）：

$$f[j] = max(f[j], f[j - w[i]] + v[i])$$

这是我们在 学习完全背包 时推导的，是经过严格证明的，具有一般性的。

然后我们只需要对「成本」&「价值」进行抽象，并结合「换元法」即可得到任意背包问题的一维优化状态转移方程。

拿我们本题的状态转移方程来分析，本题的朴素状态转移方程为：

$$f[i][j] = min(f[i - 1][j], f[i-1][j-k*coin] + k)$$

我们将硬币的面值抽象为「成本」，硬币的数量抽象「价值」，再对物品维度进行消除，即可得：

$$f[j] = min(f[j], f[j-coin] + 1)$$

如果还不理解，可以将上述四个状态转移方程「两两成对」结合来看。

代码：

[]

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

• 时间复杂度：共有 $n cnt$ 个状态需要转移，整体复杂度为 $O(n cnt)$。
• 空间复杂度：$O(cnt)$。

---

总结

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

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

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

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

建议大家加强理解 ~

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

---

最后

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

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

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

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