9.14零钱兑换（LC322-M）-Toy模板网

这篇具有很好参考价值的文章主要介绍了9.14零钱兑换（LC322-M）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

9.14零钱兑换（LC322-M）,# 9.动态规划,算法

算法：

题目中说每种硬币的数量是无限的，可以看出是典型的完全背包问题。

动规五部曲：

1.确定dp及其下标:

dp[j]：凑足总额为j所需钱币的最少个数为dp[j]

2.确定递推公式：

凑足总额为j - coins[i]的最少个数为dp[j - coins[i]]，那么只需要加上一个钱币coins[i]即dp[j - coins[i]] + 1就是dp[j]（考虑coins[i]）

所以dp[j] 要取所有 dp[j - coins[i]] + 1 中最小的。

递推公式：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);

3.dp初始化

凑足总金额为0所需钱币的个数一定是0，那么dp[0] = 0;

其他下标对应的数值呢？

考虑到递推公式的特性，dp[j]必须初始化为一个最大的数，否则就会在min(dp[j - coins[i]] + 1, dp[j])比较的过程中被初始值覆盖。

4.确定遍历顺序

本题并不强调集合是组合还是排列。

外层for循环遍历物品，内层for遍历背包

或者外层for遍历背包，内层for循环遍历物品都是可以的！

本题钱币数量可以无限使用，那么是完全背包。所以遍历的内循环是正序

5.举例推导dp数组

9.14零钱兑换（LC322-M）,# 9.动态规划,算法

初始化： 9.14零钱兑换（LC322-M）,# 9.动态规划,算法

对于当前的硬币面额，我们遍历金额 `i` 从 1 到 `amount（5）`。
如果 `i` 大于等于当前硬币的面额 `coin`，我们更新 `dp[i]` 为 `dp[i]` 和 `dp[i - coin] + 1` 的较小值。

现在，让我们逐步分析这个过程：

当 `coin` 为 1 （当`i=0`）时：
- 对于金额为 1，我们更新 `dp[1]` 为 1。对于`j=1`，`dp[1] = min(dp[1], dp[0] + 1)`，即`dp[1] = min(MAX, 0 + 1)`，此时`dp[1]`更新为`1`。
- 对于金额为 2，我们更新 `dp[2]` 为 2。对于`j=2`，`dp[2] = min(dp[2], dp[1] + 1)`，即`dp[2] = min(MAX, 1 + 1)`，此时`dp[2]`更新为`2`。
- 对于金额为 3，我们更新 `dp[3]` 为 3。对于`j=3`，`dp[3] = min(dp[3], dp[2] + 1)`，即`dp[3] = min(MAX, 2 + 1)`，此时`dp[3]`更新为`3`。
- 对于金额为 4，我们更新 `dp[4]` 为 4。
- 对于金额为 5，我们更新 `dp[5]` 为 5。
当 `coin` 为 2（当`i=1`）时：
- 对于金额为 2，我们更新 `dp[2]` 为 1。对于`j=2`，`dp[2] = min(dp[2], dp[0] + 1)`，即`dp[2] = min(2, 0 + 1)`，此时`dp[2]`为 1。
- 对于金额为 3，我们更新 `dp[3]` 为 2。对于`j=3`，`dp[3] = min(dp[3], dp[1] + 1)`，即`dp[3] = min(3, 1 + 1)`，此时`dp[3]`为 2。
- 对于金额为 4，我们更新 `dp[4]` 为 2。
- 对于金额为 5，我们更新 `dp[5]` 为 3。
当 `coin` 为 5 （当`i=2`）时：
- 对于金额为 5，我们更新 `dp[5]` 为 1。 `dp[j - coins[i]]`=dp[0]=1

正确代码：

class Solution {
    public int coinChange(int[] coins, int amount) {
        if(amount==0) return 0;
        int[] dp = new int[amount+1];
        for (int i=0; i<dp.length;i++){
            dp[i] = Integer.MAX_VALUE;
        }
        dp[0] = 0;
        for(int i=0; i<coins.length; i++){
            for(int j=coins[i]; j<=amount; j++){
                if (dp[j-coins[i]] != Integer.MAX_VALUE){
                    dp[j] = Math.min(dp[j], dp[j-coins[i]]+1);
                }
            }
        }
        if (dp[amount]==Integer.MAX_VALUE) return -1;
        return dp[amount];

    }
}

注意：

只有dp[j-coins[i]]不是初始最大值时（ if (dp[j-coins[i]] != Integer.MAX_VALUE)），该位才有选择的必要

当我们处理第`i`个硬币时，我们需要考虑以下情况：

如果`j`小于当前硬币的面额`coins[i]`，则无法使用当前的硬币来凑出金额`j`，因此`dp[j]`保持不变。
如果`j`大于等于当前硬币的面额`coins[i]`，此时我们有两种选择：
- 不使用当前的硬币，即使用`dp[j]`的值，这相当于不考虑当前的硬币，所以硬币数量不变。
- 使用当前的硬币，即使用`dp[j - coins[i]] + 1`的值，这里加1表示使用了当前的硬币，所以硬币数量加1。

因此，我们选择上述两种情况中硬币数量较少的那种，即`dp[j] = min(dp[j], dp[j - coins[i]] + 1)`。这也是为什么只有`dp[j - coins[i]]`不是初始最大值时，该位才有选择的必要。因为如果`dp[j - coins[i]]`是初始的最大值，那么意味着使用当前的硬币并不能更优地凑出金额`j`，所以我们不需要考虑这种情况，直接保持`dp[j]`不变即可。

时间空间复杂度：文章来源地址https://www.toymoban.com/news/detail-839001.html