LeetCode-322.零钱兑换-蒲公英云

LeetCode-322.零钱兑换

朱雀 2024-03-25 19:39 194阅读 0赞

题目思路

1.可以重复选，说明是重复背包问题
2.所以本题并不强调集合是组合还是排列。（建议使用组合好理解）
组合和排列一个是先遍历物品，再遍历重量，另一个是先遍历重量，在遍历物品

回溯法

突破点要定义最大值，因为我们要求最小值

class Solution {
    int ans =Integer.MAX_VALUE;
    //计算需要几个硬币
    int count = 0;
    public int coinChange(int[] coins, int amount) {
        //根据题目要求amount==0 直接为0
        if(coins == null || coins.length < 1 || amount==0){
            return 0;
        }
        backtracking(coins,amount,0,0);
        //如果还是最大值，说明没有凑成目标数
        if(ans == Integer.MAX_VALUE){
            return -1;
        }
        return ans;
    }
    private void backtracking(int[] coins,int target,int sum,int startIndex){
        if(sum == target){
            ans = Math.min(ans,count);
            return;
        }
        //剪枝
        if(sum > target){
            return;
        }
        for(int i = startIndex;i<coins.length;i++){
            sum += coins[i];
            count++;
            backtracking(coins,target,sum,i);
            sum -= coins[i];  //回溯
            count--;  //回溯
        }
    }
}

在这里插入图片描述

动态规划

class Solution {
    public int coinChange(int[] coins, int amount) {
        if(coins == null || coins.length < 1 || amount == 0){
            return 0;
        }
        int[][] dp = new int[coins.length+1][amount+1];
        for(int j = 0; j <= amount; j++){
            dp[0][j] = Integer.MAX_VALUE;
        }
        dp[0][0] = 0;
        for(int i = 1;i<=coins.length;i++){
            for(int j = 0;j<=amount;j++){
                if(j>=coins[i-1] && dp[i][j - coins[i-1]] != Integer.MAX_VALUE){
                    dp[i][j] = Math.min(dp[i-1][j], dp[i][j - coins[i-1]] + 1);
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        if(dp[coins.length][amount] == Integer.MAX_VALUE){
            return -1;
        }
        return dp[coins.length][amount];
        }
}

在这里插入图片描述

动态规划(压缩)

1.确定dp数组以及下标的含义

dp[j]：凑足总额为j所需钱币的最少个数为dp[j]

2.确定递推公式

凑足总额为j - coins[i]的最少个数为dp[j - coins[i]]，那么只需要加上一个钱币coins[i]即dp[j - coins[i]] + 1就是dp[j]（考虑coins[i]）
所以dp[j] 要取所有 dp[j - coins[i]] + 1 中最小的。
递推公式：dp[j] = Max.min(dp[j - coins[i]] + 1, dp[j]);

3.dp数组如何初始化

首先凑足总金额为0所需钱币的个数一定是0，那么dp[0] = 0;

for(int j = 0; j <= amount; j++){
            dp[0][j] = Integer.MAX_VALUE;
        }
        dp[0][0] = 0;

4.确定遍历顺序

本题求钱币最小个数，那么钱币有顺序和没有顺序都可以，都不影响钱币的最小个数。
所以本题并不强调集合是组合还是排列。
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。

5.举例推导dp数组

在这里插入图片描述
代码实现

class Solution {
    public int coinChange(int[] coins, int amount) {
        if(coins == null || coins.length < 1 || amount == 0){
            return 0;
        }
        int[] dp = new int[amount+1];
        for(int j = 0;j<dp.length;j++){
            dp[j] = Integer.MAX_VALUE;
        }
        dp[0] = 0;
        for(int i = 0;i<coins.length;i++){
            for(int j = coins[i];j<=amount;j++){
                if (dp[j - coins[i]] != Integer.MAX_VALUE) {
                    //选择硬币数目最小的情况
                    dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
                }
            }
        }
        if(dp[amount] == Integer.MAX_VALUE){
            return -1;
        }
        return dp[amount];
    }
}