【Hot 100】322. 零钱兑换

• 🙋‍♂️ 作者：海码007
• 📜 专栏：算法专栏
• 💥 标题：【Hot 100】322. 零钱兑换
• ❣️ 寄语：书到用时方恨少，事非经过不知难！

引言

零钱兑换

• 🎈 题目链接：
• 🎈 做题状态：

我的解题

开始对dp数组的定义有了一点感觉。题目是求解凑齐 amount 的最小硬币数量，所以 dp 数组就是从 0 到 amount 的一个数组。依次状态转移。直到计算出 dp[amnout]。

class Solution {
public:int coinChange(vector<int>& coins, int amount) {// dp核心三部曲：定义、转移方程、初始化vector<int> dp(amount + 1, 0);for (int i = 1; i < dp.size(); ++i){// 遍历硬币类型int minCount = INT_MAX;for (int j = 0; j < coins.size(); ++j){// 判断当前索引合法，并且上一个状态能够凑齐硬币。if (i - coins[j] >= 0 && dp[i - coins[j]] != -1){minCount = min(minCount, dp[i - coins[j]]);}}// 如果当前金额数无法凑成if (minCount == INT_MAX) {dp[i] = -1;continue;}dp[i] = minCount + 1;}return dp[amount];}
};

代码优化

class Solution {
public:int coinChange(vector<int>& coins, int amount) {// 初始化dp数组：dp[i]表示凑齐金额i所需的最小硬币数vector<int> dp(amount + 1, amount + 1); // 初始化为不可能的大值dp[0] = 0;  // 金额0需要0个硬币for (int i = 1; i <= amount; ++i) {for (int coin : coins) {if (coin <= i) { // 硬币面值不超过当前金额dp[i] = min(dp[i], dp[i - coin] + 1);}}}return dp[amount] > amount ? -1 : dp[amount];}
};

优化点分析

1. 初始化优化：

   • 原代码：dp[0]=0（隐式），其他位置在循环中计算
   • 新代码：显式设置dp[0]=0，其他位置初始化为amount+1（一个不可能达到的较大值）
   • 优势：避免了对-1的特殊判断，简化状态转移逻辑

2. 状态转移优化：

   • 原代码：需要检查dp[i-coin] != -1并维护minCount
   • 新代码：直接比较dp[i]和dp[i-coin]+1，无需中间变量
   • 优势：代码更简洁，减少分支判断，运行效率更高

3. 返回条件优化：

   • 原代码：依赖循环中设置的-1
   • 新代码：三元表达式直接判断dp[amount] > amount
   • 优势：逻辑更清晰，避免特殊值传递

复杂度分析

• 时间复杂度：O(amount * n)，其中n为硬币种类数
• 空间复杂度：O(amount)
• 优势：避免特殊值判断，减少分支预测失败，常数时间更优

边界情况处理

1. amount=0：直接返回0（dp[0]=0）
2. 无解情况：最终返回-1（dp[amount] > amount时）
3. 大金额优化：若硬币含1元，最大硬币数=amount，故amount+1是安全阈值