LeetCode 518. 零钱兑换 II

• Categories:

• Tags:

1. 题目描述
2. 思路分析
   1. 解法一：一维动态规划（推荐）
3. 相似题目

题目描述

✅ 518. 零钱兑换 II

思路分析

解法一：一维动态规划（推荐）

核心思路：

• dp[i] 表示凑成金额 i 的组合数。
• 遍历硬币，再遍历金额，确保每种硬币只使用一次顺序，避免重复。
• 转移：dp[i] += dp[i - coin]。

复杂度分析：

• 时间复杂度：O(amount * n)，其中 n 表示硬币种类数。
• 空间复杂度：O(amount)，一维数组。

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;

        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }

        return dp[amount];
    }
}

func change(amount int, coins []int) int {
	dp := make([]int, amount+1)
	dp[0] = 1

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

	return dp[amount]
}

相似题目

题目	难度	考察点
322. 零钱兑换	中等	动态规划
377. 组合总和 Ⅳ	中等	动态规划
416. 分割等和子集	中等	动态规划
494. 目标和	中等	动态规划
279. 完全平方数	中等	动态规划

本文作者: HGNULB

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

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！