LeetCode 322. 零钱兑换

Categories:

Tags:

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

题目描述

✅ 322. 零钱兑换

思路分析

本题是典型的完全背包最值问题，目标是求最少数量的硬币组合使其总和为 amount。

定义 dp[i] 表示凑出总金额为 i 所需的最小硬币数

参考代码

func coinChange(coins []int, amount int) int {
	dp := make([]int, amount+1) // 创建 dp 数组
	for i := 1; i <= amount; i++ {
		dp[i] = amount + 1 // 初始化为一个较大的值
	}

	dp[0] = 0 // 凑成金额 0 不需要任何硬币

	for _, coin := range coins {
		for i := coin; i <= amount; i++ {
			dp[i] = min(dp[i], dp[i-coin]+1) // 更新 dp 数组
		}
	}

	if dp[amount] == amount+1 {
		return -1 // 如果 dp[amount] 仍然是初始值，返回 -1
	}
	return dp[amount]
}

时间复杂度：O (n * m)，其中 n 是金额 amount，m 是硬币的数量。

空间复杂度：O (n)，用于存储 dp 数组。

➡️ 点击查看 Java 题解

write your code here

本文作者: HGNULB

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