【动态规划专题】LeetCode 322. 零钱兑换-跟着帅地玩副业，开拓第二曲线PlayOffer

宁永久会员 2023年3月19日下午7:30

最小硬币数，只能用更大的硬币尽量去替换小的

class Solution {
    public int coinChange(int[] coins, int amount) {
        //完全背包，可以使用多次，硬币顺序也没影响
        int[] dp = new int[amount + 1];
        //注意理解
        Arrays.fill(dp, 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 - coins[i]] + 1, dp[j]);
            }
        }
        return dp[amount] != Integer.MAX_VALUE ? dp[amount] : -1;
    }
}

0 赞同 0 条回复

PatNick 普通 2023年1月20日下午9:10

def coinChange(coins: list[int], amount: int) -> int:

    if amount == 0:
        return 0
    dp = [-1 for _ in range(amount + 1)]

    # dp[i]代表凑成面值为i的最少硬币个数
    dp[0] = 0

    for i in range(1, amount + 1):
        min_ = float("inf")
        # 硬币的面值
        for j in coins:
            if i - j >= 0 and dp[i-j] != -1:
                min_ = min(dp[i - j] + 1, min_)


        if min_ != float("inf"):
            dp[i] = min_

    return dp[-1]

# 优化：思路同上面一样，但两层for循环首先循环coins，但不太好理解
def coinChange( coins: list[int], amount: int) -> int:
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    # 与上面的循环方式不同，这里先循环coins
    for coin in coins:
        #内层循环在coin的基础上可以省去计算根本不用计算的循环步骤
        # 例如2块钱的硬币，如果算dp[1]肯定是-1不用算，所以dp[i]的范围肯定是要比硬币的面值大的
        # 但这种方式就不像上面那样一次性的算出dp[i]的值
        # 例如上面的方法如果计算dp[11]就等于min(dp[10],dp[9],dp[6])+1,这样一次性算出结果
        # 如果按照这个循环方式，计算dp[11]时，首先基于1元硬币的情况下，dp[11]=min(dp[11],dp[11-1]+1),当循环到2元硬币时，dp[11]=min(dp[11],dp[11-2]+1）……直到硬币的面值循环完，就是在循环硬币面值的过程中动态找到dp[10],dp[9],dp[6]的最小值
        for x in range(coin, amount + 1):
            dp[x] = min(dp[x], dp[x - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

0 赞同 0 条回复

lucca 普通 2023年1月19日下午11:14

背包变式

class Solution {
    public int coinChange(int[] coins, int amount) {
        int max = amount + 1;
        int[] f = new int[amount + 1];
        Arrays.fill(f, max);
        f[0] = 0;
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                f[j] = Math.min(f[j], f[j - coins[i]] + 1);
            }
        }
        return f[amount] == max ? -1 : f[amount];
    }
}

0 赞同 0 条回复

@ 普通 2023年1月1日下午7:00

public class Solution {

    //时间复杂的：O(N)  空间复杂度：O(N)
    public int coinChange(int[] coins, int amount) {
        int max = amount + 1;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, max);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (coins[j] <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

0 赞同 0 条回复

T 普通 2022年12月3日上午10:22

class Solution {
    public int coinChange(int[] coins, int amount) {
        if(coins.length == 0) return -1;
        // dp[n]的值： 表示的凑成总金额为n所需的最少的硬币个数
        int[] dp = new int[amount + 1];
        dp[0] = 0;
        for(int i = 1; i <= amount ; i++) {
            int min = Integer.MAX_VALUE;
            for(int j = 0; j < coins.length; j++) {
                if(i - coins[j] >= 0 && dp[i-coins[j]] < min)
                    min = dp[i-coins[j]] + 1;
            }
            dp[i] = min;
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
}

0 赞同 0 条回复

symbol 普通 2022年12月3日上午8:12

// 版本一, 先遍历物品,再遍历背包
func coinChange1(coins []int, amount int) int {
    dp := make([]int, amount+1)
    // 初始化dp[0]
    dp[0] = 0
    // 初始化为math.MaxInt32
    for j := 1; j <= amount; j++ {
        dp[j] = math.MaxInt32
    }

    // 遍历物品
    for i := 0; i < len(coins); i++ {
        // 遍历背包
        for j := coins[i]; j <= amount; j++ {
            if dp[j-coins[i]] != math.MaxInt32 {
                // 推导公式
                dp[j] = min(dp[j], dp[j-coins[i]]+1)
                //fmt.Println(dp,j,i)
            }
        }
    }
    // 没找到能装满背包的, 就返回-1
    if dp[amount] == math.MaxInt32 {
        return -1
    }
    return dp[amount]
}

// 版本二,先遍历背包,再遍历物品
func coinChange2(coins []int, amount int) int {
    dp := make([]int, amount+1)
    // 初始化dp[0]
    dp[0] = 0
    // 遍历背包,从1开始
    for j := 1; j <= amount; j++ {
        // 初始化为math.MaxInt32
        dp[j] = math.MaxInt32
        // 遍历物品
        for i := 0; i < len(coins); i++ {
            if j >= coins[i] && dp[j-coins[i]] != math.MaxInt32 {
                // 推导公式
                dp[j] = min(dp[j], dp[j-coins[i]]+1)
                //fmt.Println(dp)
            }
        }
    }
    // 没找到能装满背包的, 就返回-1
    if dp[amount] == math.MaxInt32 {
        return -1
    }
    return dp[amount]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

0 赞同 0 条回复

Tolkien 永久会员 2022年12月2日下午4:56

/**
     * 动态规划
     * 时间复杂度：O(mn)，空间复杂度：O(m)
     * 1. 凑成金额为n所需的最少硬币个数dp[n]
     * 2. dp[n] = min(dp[n-coins[k]]+1), k=0,...,coins.length-1
     * 3. 凑成金额为0所需的最少硬币个数为dp[0]=0; 0个硬币凑到金额为i的最少硬币个数为dp[i]=INF
     */
    public static int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        int max = 0x3f3f3f3f;
        Arrays.fill(dp, max);
        dp[0] = 0;

        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }

        return dp[amount] > amount ? -1 : dp[amount];
    }

0 赞同 0 条回复

訁訁訁訁訁普通 2022年11月30日下午11:22

/**
dp[i]:凑足总额为j所需钱币的最小个数为dp[i]
递推公式：
凑足总额j - coins[i]最少个数为dp[j-coins[i]]，只需要加上一个钱币coins[i]就是dp[i]
dp[j]要取所有dp[j-coins[i]]+1中最小的

初始化
dp[0]:凑足总金额为0的钱币数一定是0
dp[j]必须初始化为最大的数，否则就会在min(dp[j-coins[i]]+1,dp[j])被初始值覆盖
 */
class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        for(int i = 1;i <= amount;i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        dp[0] = 0;
        for (int i = 0;i < coins.length;i++) {
            //正序遍历，完全背包每个硬币可以选择多次
            for (int j = coins[i];j <= amount;j++) {
                //只有dp[j-coins[i]] 不是初始值的时候，才有选择的必要
                if (dp[j-coins[i]] != Integer.MAX_VALUE) {
                    dp[j] = Math.min(dp[j-coins[i]] + 1,dp[j]);
                }
            }
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
}

0 赞同 0 条回复

Mooby 普通 2022年11月29日下午10:21

public class Solution {
    public int coinChange(int[] coins, int amount) {
        int max = amount + 1;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, max);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (coins[j] <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

时间：O(Sn)，空间：O(S)

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年11月29日上午12:16

时间复杂度O（mn），空间复杂度O（n）

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        for(int i = 0;i <= amount;i++){
            dp[i] = 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 - coins[i]]+1,dp[j]);
               }

           }
       }
       return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
}

0 赞同 0 条回复

【动态规划专题】LeetCode 322. 零钱兑换

共以下 10 个回答

背包变式

# 回答此问题取消回复

【动态规划专题】LeetCode 322. 零钱兑换

共以下 10 个回答

背包变式

# 回答此问题 取消回复

# 回答此问题取消回复