LeetCode 322. 零钱兑换

322. 零钱兑换

解题思路

参考代码

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        // 初始化dp数组的元素
        Arrays.fill(dp, amount + 1);
        // 凑出金额0需要0个硬币
        dp[0] = 0;
        // 遍历每个金额，计算凑出该金额的最少硬币数
        for(int i = 1; i <= amount; i ++) {
            int temp = dp[i];
            // 遍历coins中的每个硬币
            for(int j = 0; j < coins.length; j ++) {
                // 如果当前硬币的面值 ≤ 金额i（说明可以用这个硬币），否则不能使用
                if(coins[j] <= i) {
                    temp = Math.min(temp, dp[i - coins[j]] + 1);
                }
            }
            dp[i] = temp;
        }
        // 如果最终dp[amount]还是初始值（amount+1），说明无法凑出该金额，返回-1；否则返回最少硬币数
        return dp[amount] > amount ? -1 : dp[amount];
    }
}