Minimizing Coins 题解

Minimizing Coins（最少硬币数）

题目描述

https://cses.fi/problemset/task/1634/

给定 n 种硬币，每种硬币价值为 c_i，求凑成金额 x 所需的最少硬币数（每种硬币可用无限次）。如果无法凑成，输出 -1。

限制： - 1 ≤ n ≤ 100 - 1 ≤ x ≤ 10⁶ - 1 ≤ c_i ≤ 10⁶

---

解法

问题类型：完全背包

定义：dp[j] 为凑成金额 j 所需的最少硬币数

初始条件：dp[0] = 0（金额 0 需要 0 个硬币），其他初始化为 INF

状态转移： dp[j] = min (dp[j − c_i] + 1)  for all i

解释：遍历每种硬币，尝试将硬币加到已有金额上。如果金额 i 可以用 dp[i] 个硬币凑成，那么金额 i + coin 可以用 dp[i] + 1 个硬币凑成，取所有方案中的最小值。

代码

INF = 10 ** 18
n, x = map(int, input().split())
coins = list(map(int, input().split()))

dp = [INF] * (x + 1)
dp[0] = 0

for c in coins:
    for i in range(c, x + 1):
        dp[i] = min(dp[i], dp[i - c] + 1)

print(dp[x] if dp[x] != INF else -1)

时间复杂度：O(n × x) 空间复杂度：O(x)