[322] 零钱兑换

贪心算法

details

var coinChange = function (coins, amount) {
    coins.sort((a, b) => b - a); // 按照从大到小排序

    let i = 0; // 记录所用硬币数量
    for (const coin of coins) {
        i += (amount / coin) >> 0; // 计算当前硬币最多能用几次
        amount = amount % coin; // 更新剩余金额
        if (amount === 0) {
            break; // 如果总额为 0，退出循环
        }
    }
    return amount == 0 ? i : -1; // 如果总额为 0 返回所用硬币数量，否则返回 -1
};

排序：
- 首先将硬币按从大到小的顺序排序，以便每次优先选择面值最大的硬币。
循环遍历硬币：
- 使用 for 循环遍历每个硬币。
- 对于每个硬币，计算该硬币在当前 amount 下最多能用几次，并将该数量加到 i 中。
- 更新剩余的 amount。
判断和返回：
- 如果在使用硬币后，amount 变为 0，则说明已成功找到最少的硬币数量，返回 i。
- 如果遍历完所有硬币后仍然无法凑出所需金额，返回 -1 表示无法凑出该金额。

存在的问题

这个贪心算法在某些情况下并不能保证找到最优解。特别是当硬币种类之间的面值差距不大或者当较大面值的硬币无法凑出准确的 amount 时，可能无法得到最小硬币数量。

示例

例如，对于 coins = [1, 3, 4] 和 amount = 6：

贪心算法会先选用面值为 4 的硬币一次，然后剩下 amount = 2。此时只能使用两个 1 面值的硬币，结果需要 3 枚硬币。
但最优解是使用两个 3 面值的硬币，只需 2 枚硬币。

动态规划

details

1. 状态定义

令 dp[i] 表示凑成金额 i 所需的最少硬币数量。

2. 状态转移方程

为了凑成金额 i，可以从金额 i - coin 转移而来，其中 coin 是一个硬币的面值。因此： $dp[i] = \min(dp[i - coin] + 1)$ 其中，coin 取自 coins 数组中的每一个硬币面值。

3. 边界条件

dp[0] = 0 表示凑成金额 0 需要 0 枚硬币。
对于所有大于 0 的 i，初始时设置 dp[i] 为 Infinity，表示默认无法凑成该金额。

实现代码

var coinChange = function (coins, amount) {
    let dp = new Array(amount + 1).fill(Infinity);
    dp[0] = 0; // 凑成金额 0 需要 0 个硬币

    for (let i = 1; i <= amount; i++) {
        for (let coin of coins) {
            if (i - coin >= 0) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }

    return dp[amount] === Infinity ? -1 : dp[amount];
};

复杂度分析

时间复杂度: $O(amount \times coins.length)$ $O (am o u n t \times co in s . l e n g t h)$
- 需要遍历每个金额 i 和每个硬币 coin。
空间复杂度: $O(amount)$ $O (am o u n t)$
- 需要一个长度为 amount + 1 的数组 dp。

解释和流程

初始化: dp 数组初始化为 Infinity，只有 dp[0] 为 0。
更新状态: 对于每一个 i，尝试使用每一个硬币 coin，查看能否通过 dp[i - coin] + 1 更新 dp[i] 的值。
返回结果: 如果 dp[amount] 仍为 Infinity，说明无法凑成该金额，返回 -1；否则返回 dp[amount]。

示例分析

以 coins = [1, 2, 5] 和 amount = 11 为例：

初始时，dp = [0, Infinity, Infinity, ..., Infinity]。
依次更新 dp 数组：
- dp[1] 更新为 1，使用 1 枚 1 面值的硬币。
- dp[2] 更新为 1，使用 1 枚 2 面值的硬币。
- ...
- 最终 dp[11] 更新为 3，对应的硬币组合为 [5, 5, 1]。