零钱兑换 - Stellar Observer Protocol

752 字

4 分钟

零钱兑换

2025-09-03

Algorithms

广度优先搜索

/

数组

/

动态规划

题目描述#

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

解题思路#

动态规划：
- 定义 dp[i] 表示组成金额 i 所需的最小硬币数
- 初始化 dp = 0，其他为极大值（表示不可达）
状态转移：
- 遍历每种金额，对每个硬币面额 coin
- 若 i >= coin，则 dp[i] = min(dp[i], dp[i-coin] + 1)
边界处理：
- 金额为0时不需要任何硬币
- 无法组合的金额返回-1
完全背包：
- 硬币可重复使用，类似完全背包问题
自底向上：
- 从小金额向大金额递推求解

关键洞察#

最优子结构：
- 大金额的最优解依赖小金额最优解
重叠子问题：
- 多个金额计算共享相同子问题
初始化技巧：
- 极大值设为 amount+1（最大硬币数上限）
剪枝优化：
- 硬币排序后提前终止无效计算
负数处理：
- 硬币面额需为正数，金额为正

复杂度分析#

指标	说明
时间复杂度	O(n×amount)：n 为硬币种类数
空间复杂度	O(amount)：dp 数组大小
最优情况	O(n×amount)：必须填充整个 dp 表
最坏情况	O(n×amount)：同上

代码实现#

1
/**
2
 * @param {number[]} coins
3
 * @param {number} amount
4
 * @return {number}
5
 */
6
var coinChange = function(coins, amount) {
7
    const dp = new Array(amount+1).fill(amount+1);
8
    dp[0]=0;
9
    for(let i=1;i<=amount;i++){
10
        for(const coin of coins){
11
            if(coin<=i) {
12
                dp[i] = Math.min(dp[i],dp[i-coin]+1)
13
            }
14
        }
15
    }
16
    return dp[amount] === amount+1 ? -1 : dp[amount]
17
};

1
pub fn coin_change(coins: Vec<i32>, amount: i32) -> i32 {
2
    let amount = amount as usize;
3
    let mut dp = vec![amount + 1; amount + 1];
4
    dp[0] = 0;
5

6
    for i in 1..=amount {
7
        for &coin in &coins {
8
            let coin = coin as usize;
9
            if coin <= i {
10
                dp[i] = dp[i].min(dp[i - coin] + 1);
11
            }
12
        }
13
    }
14

15
    if dp[amount] > amount {
16
        -1
17
    } else {
18
        dp[amount] as i32
19
    }
20
}

1
def coinChange(coins, amount):
2
    dp = [amount + 1] * (amount + 1)
3
    dp[0] = 0
4

5
    for i in range(1, amount + 1):
6
        for coin in coins:
7
            if coin <= i:
8
                dp[i] = min(dp[i], dp[i - coin] + 1)
9

10
    return dp[amount] if dp[amount] <= amount else -1

实际应用场景#

自动售货机：计算最少硬币找零方案`
金融系统：债券最小拆分单元计算`
游戏设计：道具合成系统资源最小消耗`
物流装箱：最小包装箱数量计算`

变种：硬币组合总数#

1
def coinCombinations(coins, amount):
2
    dp = [0] * (amount + 1)
3
    dp[0] = 1  # 金额0有1种方案（不取）
4

5
    for coin in coins:
6
        for i in range(coin, amount + 1):
7
            dp[i] += dp[i - coin]
8

9
    return dp[amount]