LeetCode85 - 零钱兑换

📝 题目描述

题目链接：零钱兑换

给你一个整数数组 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

提示：

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 2^31 - 1
• 0 <= amount <= 10^4

💡 解题思路

方法一：记忆化搜索（自顶向下的动态规划）

该问题可建模为以下优化问题：

$$\min_x \ {\textstyle \sum_{i=0}^{n-1}} x_i \quad \text{subject to} \quad \ {\textstyle \sum_{i=0}^{n-1}} x_i \times c_i = S$$

其中，$S$ 是总金额，$c_i$ 是第 $i$ 枚硬币的面值，$x_i$ 是面值为 $c_i$ 的硬币数量，由于 $x_i×c_i$ 不能超过总金额 $S$，可以得出 $x_i$ 最多不会超过 $\frac{S}{c_i}$，所以 $x_i$ 的取值范围为 $[0,\frac{S}{c_i}]$。

一个简单的解决方案是通过回溯的方法枚举每个硬币数量子集 $[x_0… x_{n−1}]$，针对给定的子集计算它们组成的金额数，如果金额数为 $S$，则记录返回合法硬币总数的最小值，反之返回 $−1$。

该做法的时间复杂度为 $O(S^n)$，会超出时间限制，因此必须加以优化。

我们能改进上面的指数时间复杂度的解吗？当然可以，利用动态规划，我们可以在多项式的时间范围内求解。首先，我们定义：

• $F(S)$：组成金额 $S$ 所需的最少硬币数量
• $[c_0…c_{n−1}]$：可选的 $n$ 枚硬币面额值

我们注意到这个问题有一个最优的子结构性质，这是解决动态规划问题的关键。最优解可以从其子问题的最优解构造出来。如何将问题分解成子问题？假设我们知道 $F(S)$，即组成金额 $S$ 最少的硬币数，最后一枚硬币的面值是 $C$。那么由于问题的最优子结构，转移方程应为：

$$F(S)=F(S−C)+1$$

但我们不知道最后一枚硬币的面值是多少，所以我们需要枚举每个硬币面额值 $c_0,c_1,c_2…c_{n−1}$ 并选择其中的最小值。下列递推关系成立：

$$F(S) = \min_{i=0 \ldots n-1} F(S - c_i) + 1 \quad \text{subject to} \quad S - c_i \ge 0 \\ F(S)=0 ,when\ S=0 \\ F(S)=−1 ,when\ n=0$$

在上面的递归树中，我们可以看到许多子问题被多次计算。例如，$F(1)$ 被计算了 $13$ 次。为了避免重复的计算，我们将每个子问题的答案存在一个数组中进行记忆化，如果下次还要计算这个问题的值直接从数组中取出返回即可，这样能保证每个子问题最多只被计算一次。

方法二：自底向上的动态规划

我们采用自下而上的方式进行思考。仍定义 $F(i)$ 为组成金额 $i$ 所需最少的硬币数量，假设在计算 $F(i)$ 之前，我们已经计算出 $F(0)−F(i−1)$ 的答案。 则 $F(i)$ 对应的转移方程应为

$$F(i) = \min\nolimits_{j=0 \ldots n-1} F(i - c_j) + 1$$

其中 $c_j$ 代表的是第 $j$ 枚硬币的面值，即我们枚举最后一枚硬币面额是 $c_j$，那么需要从 $i−c_j$ 这个金额的状态 $F(i−c_j)$ 转移过来，再算上枚举的这枚硬币数量 $1$ 的贡献，由于要硬币数量最少，所以 $F(i)$ 为前面能转移过来的状态的最小值加上枚举的硬币数量 $1$。

例子1:

假设

coins = [1, 2, 5], amount = 11

则，当 $i==0$ 时无法用硬币组成，为 $0$ 。当 $i<0$ 时，忽略 $F(i)$

F(i)	最小硬币数量
F(0)	0 //金额为0不能由硬币组成
F(1)	1 //$F(1)=min(F(1−1),F(1−2),F(1−5))+1=1$
F(2)	1 //$F(2)=min(F(2−1),F(2−2),F(2−5))+1=1$
F(3)	2 //$F(3)=min(F(3−1),F(3−2),F(3−5))+1=2$
F(4)	2 //$F(4)=min(F(4−1),F(4−2),F(4−5))+1=2$
…	…
F(11)	3 //$F(11)=min(F(11−1),F(11−2),F(11−5))+1=3$
我们可以看到问题的答案是通过子问题的最优解得到的。

例子2：

假设

coins = [1, 2, 3], amount = 6

在上图中，可以看到：

$$\begin{aligned} F(3) &= \min\bigl(F(3 - c_1), F(3 - c_2), F(3 - c_3)\bigr) + 1 \\ &= \min\bigl(F(3 - 1), F(3 - 2), F(3 - 3)\bigr) + 1 \\ &= \min\bigl(F(2), F(1), F(0)\bigr) + 1 \\ &= \min(1, 1, 0) + 1 \\ &= 1 \end{aligned}$$

🔧 代码实现

1、记忆化搜索（自顶向下的动态规划）

class Solution {
    vector<int>count;
    int dp(vector<int>& coins, int rem) {
        if (rem < 0) return -1;
        if (rem == 0) return 0;
        if (count[rem - 1] != 0) return count[rem - 1];
        int Min = INT_MAX;
        for (int coin:coins) {
            int res = dp(coins, rem - coin);
            if (res >= 0 && res < Min) {
                Min = res + 1;
            }
        }
        count[rem - 1] = Min == INT_MAX ? -1 : Min;
        return count[rem - 1];
    }
public:
    int coinChange(vector<int>& coins, int amount) {
        if (amount < 1) return 0;
        count.resize(amount);
        return dp(coins, amount);
    }
};

2、自底向上的动态规划

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, -1);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            int minn = INT_MAX;
            for (int coin : coins) {
                if ((i - coin >= 0) && (dp[i - coin] != -1)) {
                    minn = min(dp[i - coin], minn);
                }
            }
            dp[i] = minn == INT_MAX ? -1 : minn + 1;
        }
        return dp[amount];
    }
};

📊 复杂度分析

1、记忆化搜索（自顶向下的动态规划）

• 时间复杂度：$O(Sn)$，其中 $S$ 是金额，$n$ 是面额数。我们一共需要计算 $S$ 个状态的答案，且每个状态 $F(S)$ 由于上面的记忆化的措施只计算了一次，而计算一个状态的答案需要枚举 $n$ 个面额值，所以一共需要 $O(Sn)$ 的时间复杂度。
• 空间复杂度：$O(S)$，我们需要额外开一个长为 $S$ 的数组来存储计算出来的答案 $F(S)$。

2、自底向上的动态规划

• 时间复杂度：$O(Sn)$，其中 $S$ 是总金额 amount，$n$ 是面额数组 coins 的长度。因为外层循环需要执行 $S$ 次（计算金额 $1$ 到 $S$），内层循环需要执行 $n$ 次（遍历所有硬币），两者是嵌套关系。
• 空间复杂度：$O(S)$，需要一个长度为 amount + 1 的 dp 数组来存储中间状态。

🎯 总结

• 核心思想：理解两种动态规划的模板写法。