Minimizing Coins 题解

题目描述

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

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

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

解法

完全背包 DP

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

状态转移：

dp[j] = min(dp[j - c_i] + 1)  for all i

基准情况：dp[0] = 0（金额 0 需要 0 个硬币）

代码

n, target = map(int, input().split())
arr = [int(x) for x in input().split()]

INF = 10**7  # 足够大的值

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

for coin in arr:
    for i in range(target - coin + 1):
        dp[i + coin] = min(dp[i + coin], dp[i] + 1)

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

复杂度

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

解释

这是一个完全背包问题（每种硬币可用无限次）。

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