LeetCode 518. 零钱兑换 II

题目描述

✅ 518. 零钱兑换 II

image-20250507222013360

image-20250507221913737

思路分析

完全背包组合问题

⚠️ 注意：必须先遍历硬币，再遍历金额，否则会统计成排列数而不是组合数。

image-20250507223007644

参考代码



1
2
3
4
5
6
7
8
9
10
11
12
13



func change(amount int, coins []int) int {
	// 定义 dp[i] 表示组成金额 i 的组合数
	var dp []int = make([]int, amount+1)
	dp[0] = 1 // 组成 0 的方法只有一种

	for _, coin := range coins {
		for j := coin; j <= amount; j++ {
			dp[j] += dp[j-coin]
		}
	}

	return dp[amount]
}
  • 时间复杂度：O(n * amount)，其中 n 是硬币数量。
  • 空间复杂度：O(amount)，只使用了一维数组。

➡️ 点击查看 Java 题解



1



write your code here

相似题目

image-20250510203046556

完全背包组合问题总结

image-20250510203200463

本文作者:
本文链接: https://hgnulb.github.io/blog/2025/99921078
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！