【LeetCode】【算法】322. 零钱兑换

LeetCode 322. 零钱兑换

题目

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回-1。
你可以认为每种硬币的数量是无限的。
示例：
输入：coins = [1, 2, 5], amount = 11
输出：3
解释：11 = 5 + 5 + 1

思路

思路：动态规划，dp[]数组表示组成金额i需要的最少硬币个数

1. 数组初始化：Arrays.fill(dp, amount + 1); 相当于给一个最大值，便于后面比较得到最少硬币枚数。dp[0]=0，组成金额0只需要0枚硬币
2. 嵌套循环：
   I. 第一个循环for(int i=1; i<amount+1; i++)从金额1~金额i，最少的硬币数量
   II. 第二个循环for (int coin:coins)，假设使用该面额的硬币，能否组成目标金额。里面的条件是if(coin <= i)，因为如果coin>i那么这枚硬币肯定用不上
   在if语句中，dp[i]=Math.min(dp[i-coin]+1,dp[i])，这个递推式的意思是说：如果使用coin的话，此时硬币数量就=1+金额(i-coin)的最少硬币数量，看看dp[i]本身和dp[i-coin]+1哪个更小。
3. return dp[amount] > amount ? -1 : dp[amount]; 也就是如果dp[amount]没有变化，那就表示没有解，否则返回解

结果

class Solution {
    public int coinChange(int[] coins, int amount) {
        if (amount == 0) return 0;
        // 贪心 -> 不可行，因为最优解未必通过贪心结果组成。如果贪心最大面值的硬币，结果可能是由部分小硬币组成的（因为大硬币无法组成目标面额）
        int[] dp = new int[amount + 1]; // 动态规划数组表示组成目标金额需要几枚硬币
        // 初始化dp数组
        Arrays.fill(dp, amount + 1);
        dp[0] = 0; // 如果组成金额0需要0枚硬币
        for (int i = 1; i < amount + 1; i++) {
            for (int coin : coins) { // 每个面额下的硬币
                if (coin <= i){ // 如果硬币面额 < 当前所需组成的amount
                    // 要么使用coin：此时硬币数量=1+(目标amount-指定面额)硬币数量
                    // 要么不用coin：此时硬币数量=目标amount硬币数量
                    dp[i] = Math.min(dp[i - coin] + 1, dp[i]);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}