LeetCode LCR 103. 零钱兑换

Categories:

题目描述
思路分析
1. 解法一：动态规划（完全背包，推荐）
相似题目

题目描述

✅ LCR 103. 零钱兑换

思路分析

解法一：动态规划（完全背包，推荐）

核心思路：

硬币可重复使用，属于完全背包问题，目标是求凑出 amount 的最少硬币数（最值型）。

状态定义：dp[i] 表示凑出金额 i 所需的最少硬币数。

状态转移：枚举每种硬币 coin，若 i >= coin，则： dp[i] = min(dp[i], dp[i - coin] + 1) 含义：从金额 i - coin 的状态出发，再用一枚 coin 面值的硬币凑成 i。

初始化：dp[0] = 0（凑出 0 不需要硬币），其余初始化为 amount + 1（表示不可达，安全上界）。

遍历顺序：外层枚举硬币，内层正序枚举金额（完全背包正序，保证硬币可重复使用）。

返回值：若 dp[amount] > amount，说明无法凑出，返回 -1；否则返回 dp[amount]。

复杂度分析：

时间复杂度：O(n × amount)，其中 n 为硬币种类数，amount 为目标金额

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

class Solution {
    public int coinChange(int[] coins, int amount) {
        // dp[i] 表示凑出金额 i 所需的最少硬币数
        int[] dp = new int[amount + 1];
        // 初始化为不可达状态（amount + 1 作为安全上界）
        Arrays.fill(dp, amount + 1);
        // 凑出金额 0 不需要任何硬币
        dp[0] = 0;
        // 外层枚举硬币，内层正序枚举金额（完全背包）
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                // 状态转移：选或不选当前硬币取最小值
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
        // dp[amount] 仍为初始值说明无法凑出
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

func coinChange(coins []int, amount int) int {
    // dp[i] 表示凑出金额 i 所需的最少硬币数
    dp := make([]int, amount+1)
    // 初始化为不可达状态（amount + 1 作为安全上界）
    for i := 1; i <= amount; i++ {
        dp[i] = amount + 1
    }
    // 凑出金额 0 不需要任何硬币
    dp[0] = 0
    // 外层枚举硬币，内层正序枚举金额（完全背包）
    for _, coin := range coins {
        for i := coin; i <= amount; i++ {
            // 状态转移：选或不选当前硬币取最小值
            if dp[i-coin]+1 < dp[i] {
                dp[i] = dp[i-coin] + 1
            }
        }
    }
    // dp[amount] 仍为初始值说明无法凑出
    if dp[amount] == amount+1 {
        return -1
    }
    return dp[amount]
}

相似题目

题目	难度	考察点
279. 完全平方数	中等	完全背包、动态规划
518. 零钱兑换 II	中等	完全背包、组合计数
983. 最低票价	中等	动态规划、最优化
377. 组合总和 Ⅳ	中等	完全背包、有序计数
139. 单词拆分	中等	完全背包、可行性判断
91. 解码方法	中等	线性动态规划
416. 分割等和子集	中等	0-1 背包

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/17539201