零钱兑换

零钱兑换

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

        for( int i = 0 ; i <= m ; i++){
            for( int j = 0 ; j <= amount ;j++){
                //赋不能组成的值
                dp[i][j] = amount + 1;
            }
        }
        //使用前i种硬币，凑出总金额j所需的最少硬币个数，初始为0
        dp[0][0] = 0;

        for(int i = 1;i <= m;i++){
            for(int j = 0;j < amount + 1;j++){
                //背包容量超过，此处硬币面值大于目标金额
                if(coins[i - 1] > j){
                    dp[i][j] = dp[i - 1][j];
                }else{
                    //没有超过，取决于上一个或dp[i][j - coins[i - 1]]加自己这一枚硬币
                    dp[i][j] = Math.min(dp[i - 1][j],dp[i][j - coins[i - 1]]+1);
                }
            }
        }
        return dp[m][amount] == amount + 1 ? -1 : dp[m][amount];
    }
}
或
class Solution {
    public int coinChange(int[] coins, int amount) {
        // dp[i] 表示凑成金额 i 所需的最少硬币数
        int[] dp = new int[amount + 1];
        
        // 初始化：除了dp[0]=0，其他都设为最大值（表示不可达）
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        
        // 完全背包：正序遍历所有金额
        for (int i = 1; i <= amount; i++) {
            // 遍历所有硬币面额
            for (int coin : coins) {
                // 如果当前金额大于等于硬币面额
                if (i >= coin) {
                    // 状态转移：选择当前硬币或不选择
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        
        // 如果dp[amount]仍然大于amount，说明无法凑出(因为初始化的时候初始的不可能达到的数量金额加一)
        return dp[amount] > amount ? -1 : dp[amount];
    }
}
或
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 = 0;i < coins.length;i++){
            int cost = coins[i];
            for(int j = cost;j < amount + 1;j++){
                dp[j] = Math.min(dp[j],dp[j - cost]+1);
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

零钱兑换 II

class Solution {
    public int change(int amount, int[] coins) {
        int m = coins.length + 1;
        int n = amount + 1;
        int[][] dp = new int[m][n];

        for(int i = 0;i < m;i++){
            //使用前i种硬币，凑出总金额j的方案
            dp[i][0] = 1;
        }

        for(int i = 1;i < m;i++){
            for(int j = 0;j < n;j++){
                if(j < coins[i - 1]){
                    //等于不考虑使用当前这枚硬币的情况
                    dp[i][j] = dp[i - 1][j];
                }else{
                    //完全忽略第 i种硬币，只使用前 i-1种硬币来凑金额 j的方案加上在不使用更多当前硬币的前提下，凑出金额 j - coins[i-1]的组合数
                    dp[i][j] = dp[i - 1][j]+dp[i][j - coins[i - 1]];
                }
            }
        }
        return dp[m - 1][n - 1];
    }
}