企业官网建设流程全解析

零钱兑换问题

一、问题描述

题目要求

给定不同面额的硬币coins和一个总金额amount，编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回-1。

示例

• 输入：coins = [1,2,5], amount = 11

• 输出：3（解释：11 = 5 + 5 + 1，最少需要 3 枚硬币）

• 输入：coins = [2], amount = 3

• 输出：-1（解释：无法用面额 2 的硬币凑出 3）

核心难点

1. 需找到 “最少硬币数”，而非所有组合数；
2. 需处理 “无法凑出金额” 的边界情况；
3. 避免数组越界、数值溢出等编码错误。

二、解题思路：动态规划（DP）

1. 状态定义

定义dp[i]表示：凑成总金额i所需的最少硬币数量。

2. 初始化

• 基准条件：dp[0] = 0，因为凑 0 元不需要任何硬币。
• 其他状态：初始化dp[i] = amount + 1，amount+1是一个 “大于最大可能值” 的数，代表 “初始不可达”。最大可能值是amount（全用 1 元硬币），因此amount+1可标记为 “未更新”。

3. 状态转移

对于每个金额i（从 1 到amount），遍历所有硬币面额coin：

• 若coin <= i（当前硬币面额不超过目标金额），则：dp[i] = min(dp[i], dp[i - coin] + 1)
• 解释：dp[i - coin]是凑出i - coin元的最少硬币数，加 1 枚当前硬币即可凑出i元，取所有可能中的最小值。

4. 结果判断

• 若dp[amount] > amount：说明始终未更新，无法凑出金额，返回-1；
• 否则：返回dp[amount]（最少硬币数）。

三、完整代码实现

class Solution { public: int coinChange(vector<int>& coins, int amount) { vector<int> dp(amount + 1, amount + 1); dp[0] = 0; for (int i = 1; i <= amount; ++i) { for (int j = 0; j < coins.size(); ++j) { if (coins[j] <= i) { dp[i] = min(dp[i], dp[i - coins[j]] + 1); } } } return dp[amount] > amount ? -1 : dp[amount]; } };

四、复杂度分析

• 时间复杂度：O(amount * len(coins))外层循环遍历amount个金额，内层循环遍历所有硬币，总次数为两者乘积。
• 空间复杂度：O(amount)仅需维护一个大小为amount + 1的 dp 数组，属于线性空间。

五、总结

问题的核心是动态规划的状态转移思想：将 “凑金额 i” 的大问题，拆解为 “凑金额 i-coin” 的小问题