leetcode 322. Coin Change | 322. 零钱兑换（动态规划）-蒲公英云

leetcode 322. Coin Change | 322. 零钱兑换（动态规划）

向右看齐 2022-10-20 00:55 349阅读 0赞

题目

https://leetcode.com/problems/coin-change/
在这里插入图片描述

题解

也许是第一次在没看答案的情况下写的动态规划…

第一反应是，这题不是广义背包吗？想了一下，不是，因为广义背包的约束是小于等于容量，而本题的约束是等于容量。

第二反应是，这题有点像 dp 的累加和啊。把一个数 a 可以拆成 b + c，这样就划分成了子问题。

第三反应是，拆分的过程有点类似于 线段树，可以用来方便理解，不过思路不能照搬。

结合这三个想法，确定了 dp[] 表示强制包含当前元素情况下，需要的最小硬币数量，然后就开始草稿尝试 dp 了。写了几行之后，发现思路可行，搞定。
在这里插入图片描述

class Solution { 
    public int coinChange(int[] coins, int amount) { 
        Arrays.sort(coins);
        int[] dp = new int[amount + 1]; // 强制包含当前元素情况下，需要的最小硬币数量
        for (int i = 1; i < amount + 1; i++) { 
            int minCount = Integer.MAX_VALUE;
            for (int coin : coins) { 
                if (coin >= i) { 
                    if (coin == i) minCount = 1;
                    break;
                }
                if (dp[i - coin] != Integer.MAX_VALUE)
                    minCount = Math.min(minCount, 1 + dp[i - coin]);
                 // minCount = Math.min(minCount, dp[coin] + dp[i - coin]);
            }
            dp[i] = minCount;
        }
        if (dp[amount] == Integer.MAX_VALUE) return -1;
        else return dp[amount];
    }
}