Coin Combinations

完全背包类型一：计数问题（方案数）

Coin Combinations I（有序）

题目描述

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

给定 n 种硬币，每种硬币价值为 $c_i$，求凑成金额 x 的不同方式数（顺序不同视为不同）。输出模 $10^9+7$ 的结果。

限制：

• 1 ≤ n ≤ 100
• 1 ≤ x ≤ $10^6$
• 1 ≤ c_i ≤ $10^6$

示例：

• 输入：3 9, coins = [2, 3, 5]
• 输出：8（9 = 2+2+5, 2+5+2, 5+2+2, 3+3+3, 2+2+2+3, 2+2+3+2, 2+3+2+2, 3+2+2+2））

解法

问题类型：完全背包（计数问题，每种硬币可用无限次）

定义：dp[w] 为凑成金额 w 的方式数

初始条件：dp[0] = 1（金额为 0 有一种方式：什么都不选）

状态转移：

$$dp[w] = \sum_{i=1}^{n} dp[w - c_i]$$

代码

MOD = 10**9 + 7

n, x = map(int, input().split())
coins = list(map(int, input().split()))

dp = [0] * (x + 1)
dp[0] = 1
for i in range(1, x + 1):
    for c in coins:
        if i - c >= 0:
            dp[i] = (dp[i] + dp[i - c]) % MOD

print(dp[x])

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

---

Coin Combinations II（无序）

题目描述

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

给定 n 种硬币，每种硬币价值为 $c_i$，求凑成金额 x 的无序方式数（顺序不同视为相同）。输出模 $10^9+7$ 的结果。

限制：

• 1 ≤ n ≤ 100
• 1 ≤ x ≤ $10^6$
• 1 ≤ c_i ≤ $10^6$

示例：

• 输入：3 9, coins = [2, 3, 5]
• 输出：3（只计 {2,2,5}, {3,3,3}, {2,2,2,3}，不区分顺序）

解法

问题类型：完全背包（计数问题，每种硬币可用无限次）

关键差异：与 Coin Combinations I 不同，本题要求无序方式数，即 1+3 和 3+1 视为相同。

定义：dp[w] 为凑成金额 w 的无序方式数

初始条件：dp[0] = 1（金额为 0 有一种方式：什么都不选）

状态转移：

$$dp[w] = \sum_{i=1}^{n} dp[w - c_i]$$

代码

import sys
MOD = 10**9 + 7
input = sys.stdin.readline

n, x = map(int, input().split())
coins = list(map(int, input().split()))

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

for c in coins:
    for i in range(x + 1):
        if i - c >= 0:
            dp[i] = (dp[i - c] + dp[i]) % MOD

print(dp[x])

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

---

有序 vs 无序的区别

遍历顺序	结果	说明
先遍历金额 for i in range(x) → 后遍历硬币	有序	每种硬币组合计数多次（顺序不同视为不同）
先遍历硬币 for c in coins → 后遍历金额	无序	每种硬币组合只计数一次（顺序不同视为相同）