题型归类🔍_零钱兑换系列

1️⃣.零钱兑换I

题目:可以凑成总金额所需的最少的硬币个数

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        Arrays.fill(dp,amount+1);
        dp[0]=0;

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

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

2️⃣.零钱兑换II

题目:请你计算并返回可以凑成总金额的硬币组合数

class Solution {
    public int change(int amount, int[] coins) {
        int[]dp=new int[amount+1];
        
        dp[0]=1;

        for(int co:coins){
            for(int i=co;i<=amount;++i){
                dp[i]+=dp[i-co];
            }
        }

        return dp[amount];
    }
}

2.总结提炼🎯