LeetCodehot 力扣热题100 零钱兑换

时间：2025-03-12 17:58:53

详细运行思路

这段代码使用动态规划（Dynamic Programming, DP）解决最少硬币找零问题。

它的核心思想是：

状态转移方程：

dp[i] = min(dp[i], dp[i - coins[j]] + 1)

表示兑换 i 元最少需要的硬币数，取决于使用 coins[j] 后的最优解。

代码讲解

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, amount + 1); // 初始化 dp 数组，默认值为 amount+1（相当于无穷大）
        dp[0] = 0; // 兑换 0 元需要 0 个硬币

        for (int i = 1; i <= amount; i++) {  // 遍历所有金额
            for (int j = 0; j < coins.size(); j++) {  // 遍历所有硬币
                if (i >= coins[j]) {  // 硬币 coins[j] 只能用于兑换大于等于它的金额
                    dp[i] = min(dp[i], dp[i - coins[j]] + 1);  // 状态转移
                }
            }
        }

        return dp[amount] == (amount + 1) ? -1 : dp[amount]; // 返回结果
    }
};

详细运行步骤

假设 coins = [1, 2, 5]，amount = 11，来看代码如何执行。

初始化

vector<int> dp(amount + 1, amount + 1); // dp[0..11] 赋值为 amount+1（12）
dp[0] = 0; // 兑换 0 元需要 0 个硬币

初始 dp 数组：

dp[0]  =  0
dp[1]  =  12
dp[2]  =  12
dp[3]  =  12
dp[4]  =  12
dp[5]  =  12
dp[6]  =  12
dp[7]  =  12
dp[8]  =  12
dp[9]  =  12
dp[10] =  12
dp[11] =  12

第一层循环：遍历金额

i = 1

遍历硬币：

• 硬币 1：可以兑换 1 元，dp[1] = min(dp[1], dp[1-1] + 1) = min(12, 0 + 1) = 1

• 硬币 2：无法兑换 1 元（跳过）

• 硬币 5：无法兑换 1 元（跳过）

更新 dp[1] = 1

dp[0]  =  0
dp[1]  =  1
dp[2]  =  12
dp[3]  =  12
dp[4]  =  12
dp[5]  =  12
dp[6]  =  12
dp[7]  =  12
dp[8]  =  12
dp[9]  =  12
dp[10] =  12
dp[11] =  12

i = 2

遍历硬币：

• 硬币 1：dp[2] = min(dp[2], dp[2-1] + 1) = min(12, 1 + 1) = 2

• 硬币 2：dp[2] = min(dp[2], dp[2-2] + 1) = min(2, 0 + 1) = 1

• 硬币 5：无法兑换 2 元（跳过）

更新 dp[2] = 1

dp[0]  =  0
dp[1]  =  1
dp[2]  =  1
dp[3]  =  12
dp[4]  =  12
dp[5]  =  12
dp[6]  =  12
dp[7]  =  12
dp[8]  =  12
dp[9]  =  12
dp[10] =  12
dp[11] =  12

i = 3

遍历硬币：

• 硬币 1：dp[3] = min(dp[3], dp[3-1] + 1) = min(12, 1 + 1) = 2

• 硬币 2：dp[3] = min(dp[3], dp[3-2] + 1) = min(2, 1 + 1) = 2

• 硬币 5：无法兑换 3 元（跳过）

更新 dp[3] = 2

dp[0]  =  0
dp[1]  =  1
dp[2]  =  1
dp[3]  =  2
dp[4]  =  12
dp[5]  =  12
dp[6]  =  12
dp[7]  =  12
dp[8]  =  12
dp[9]  =  12
dp[10] =  12
dp[11] =  12

i = 4

遍历硬币：

• 硬币 1：dp[4] = min(dp[4], dp[4-1] + 1) = min(12, 2 + 1) = 3

• 硬币 2：dp[4] = min(dp[4], dp[4-2] + 1) = min(3, 1 + 1) = 2

• 硬币 5：无法兑换 4 元（跳过）

更新 dp[4] = 2

dp[0]  =  0
dp[1]  =  1
dp[2]  =  1
dp[3]  =  2
dp[4]  =  2
dp[5]  =  12
dp[6]  =  12
dp[7]  =  12
dp[8]  =  12
dp[9]  =  12
dp[10] =  12
dp[11] =  12

继续计算 dp[5] 到 dp[11]，最终得到：

dp[0]  =  0
dp[1]  =  1
dp[2]  =  1
dp[3]  =  2
dp[4]  =  2
dp[5]  =  1
dp[6]  =  2
dp[7]  =  2
dp[8]  =  3
dp[9]  =  3
dp[10] =  2
dp[11] =  3

最终结果

return dp[amount] == (amount + 1) ? -1 : dp[amount];

• dp[11] = 3

• 所以最少需要 3 枚硬币兑换 11（可能的组合：5 + 5 + 1）

总结

• 时间复杂度：O(n × m)（n 是 amount，m 是 coins.size()）

• 空间复杂度：O(n)（dp 数组）

相关文章