LeetCode 322. 零钱兑换

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

🔥 322. 零钱兑换

思路分析

完全背包最值问题

参考代码

func coinChange(coins []int, amount int) int {
	// 初始化 dp 数组，初始值为 amount+1
	// dp[i] 表示凑成金额 i 所需的最少硬币数量
	dp := make([]int, amount+1)
	for i := range dp {
		dp[i] = amount + 1
	}
	// 凑成金额 0 所需的硬币数量为 0
	dp[0] = 0
	// 动态规划计算硬币数量
	for i := 1; i <= amount; i++ {
		for _, coin := range coins {
			if i >= coin {
				dp[i] = min(dp[i], dp[i-coin]+1)
			}
		}
	}
	// 如果 dp[amount] 仍然是初始值，表示无解
	if dp[amount] == amount+1 {
		return -1
	}
	return dp[amount]
}

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

func coinChange(coins []int, amount int) int {
	// 创建一个数组 dp，dp[i] 表示兑换金额 i 所需的最少硬币数量
	dp := make([]int, amount+1)

	// 初始化 dp 数组，将其所有值初始化为一个不可能的大数，比如 math.MaxInt32
	for i := range dp {
		dp[i] = math.MaxInt32
	}

	// 设置兑换金额为 0 需要 0 个硬币
	dp[0] = 0

	// 动态规划计算最小硬币数量
	for i := 1; i <= amount; i++ {
		for _, coin := range coins {
			if i-coin >= 0 {
				dp[i] = min(dp[i], dp[i-coin]+1)
			}
		}
	}

	// 如果 dp[amount] 仍然是 math.MaxInt32，则说明无法兑换，返回 -1，否则返回 dp[amount]
	if dp[amount] == math.MaxInt32 {
		return -1
	}
	return dp[amount]
}

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

🍏 点击查看 Java 题解

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1]; // dp[i] 表示凑成金额 i 所需的最少硬币数量
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }
}

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/89162014