零钱兑换

🟡 Medium · 🏷️ 数组、动态规划（完全背包） · LeetCode#322

📖 题目

给定几种面额的硬币（每种可以无限用）和目标金额 amount，求凑出这个金额最少要几枚硬币，凑不出返回 -1。

输入	输出
coins=[1,3,4], amount=6	2（3+3）

💡 思路

贪心不行：coins=[1,3,4], amount=6，贪心会先选面值最大的 4，再补 1+1，一共 3 枚；但 3+3 只要 2 枚。局部最优不等于全局最优，必须老老实实用 DP 把每种可能都试一遍。

dp[i] 表示凑出金额 i 最少要几枚硬币。对每种硬币面额 c，如果 i >= c，就可以试试"用这枚硬币"：dp[i] = min(dp[i], dp[i-c] + 1)。

初始化：dp[0] = 0（凑0元不需要硬币），其余先设成一个不可能达到的大值（amount + 1——因为最多用 amount 枚1元硬币就够了，超过这个数肯定是还没被更新过，代表凑不出）。

💻 代码

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [amount + 1] * (amount + 1)
        dp[0] = 0
        for i in range(1, amount + 1):
            for c in coins:
                if i >= c:
                    dp[i] = min(dp[i], dp[i - c] + 1)
        return dp[-1] if dp[-1] <= amount else -1

时间复杂度 O(amount × len(coins))，空间复杂度 O(amount)。i - c 一定要先判断 i >= c 才能用，否则 Python 的负数下标会绕到列表末尾取到一个无关的值，而不是报错——这个坑不容易一眼看出来。

这类"每种物品可以无限选"的背包问题叫完全背包，跟之前网格类的路径 DP（不同路径）不是一回事：路径 DP 是二维表格，从上方/左方转移；背包 DP 是一维数组，对每个物品决定"要不要用它"。