零钱兑换

GitHub跳转原题关系图返回列表

完全背包 DP：dp[i] 从所有硬币面额转移，取最小值，不可达用哨兵标记。

OJ: leetcodecn

题目 ID: coin-change

难度:普及+/提高-

标签:动态规划完全背包

创建: 2026-07-29 12:38

更新: 2026-07-29 15:20

后置题目
luogu P3891[GDOI2014] 采集资源B 的 gain[x] 就是 A 那种完全背包升序转移的复用，只是把 min(最少硬币数) 换成 max(最多新增采集效率)，再叠加按时间推进的状态 DPluogu P1450[HAOI2008] 硬币购物B 的第一步直接复用 A 教的“硬币无限使用”完全背包（一维金额 dp、由 dp[x-c] 转移），只把 A 的最少硬币数语义换成方案数累加 dp[x]+=dp[x-c] 做预处理，再在其上用 16 个子集容斥扣掉超上界方案，属 A 之上叠加容斥流程。luogu P2851[USACO06DEC] The Fewest Coins GB 的「找零方 DP」原样复用 A 教的完全背包最小值转移（B 代码里就是 change_dp 那一层），把它当作两个 DP 中较简单的第二半，B 的额外难度在付款方的多重背包单调队列优化

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

给定硬币面额和金额，求最少硬币数。每种硬币无限使用。

思路

dp[i] 表示凑成金额 i 的最少硬币数。dp[i] = min(dp[i-c] + 1) 对所有 c <= i。初值 dp[0] = 0，其余 amount + 1（不可达哨兵）。最终 dp[amount] > amount 则无解。

代码

cpp
#include <bits/stdc++.h>
using namespace std;

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 c : coins)
                if (i >= c)
                    dp[i] = min(dp[i], dp[i - c] + 1);
        return dp[amount] > amount ? -1 : dp[amount];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, amt;
    cin >> n >> amt;
    vector<int> a(n);
    for (int &x : a)
        cin >> x;
    cout << Solution().coinChange(a, amt) << '\n';
    return 0;
}
python
#!/usr/bin/env python3
from typing import List


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 -1 if dp[amount] > amount else dp[amount]


def main():
    n, amt = map(int, input().split())
    a = list(map(int, input().split()))
    print(Solution().coinChange(a, amt))


if __name__ == "__main__":
    main()

复杂度

  • 时间复杂度：O(n⋅amount)O(n \cdot \text{amount})。
  • 空间复杂度：O(amount)O(\text{amount})。

总结

零钱兑换是完全背包求最少物品数的经典题。不可达哨兵用 amount + 1（而非 INF），因为最多用 amount 个 1 元硬币。