#P3900. 兑换硬币
-
1000ms
Tried: 25
Accepted: 4
Difficulty: 4
-
算法标签>动态规划
兑换硬币
解题思路
本题等价于把正整数 n 划分为恰好 k 个正整数的有序序列。直接的划分型动态规划如下:
设 dp[s][t] 表示用恰好 t 枚硬币,面额之和为 s 的有序方案数。
转移时,最后一枚硬币取值为 x (1 ≤ x ≤ s),那么前面 t-1 枚的和是 s-x,于是:
边界:dp[0][0] = 1(选 0 枚凑出和 0 的方案为 1),其他如 dp[s][0]=0 (s>0)。
因为题目给的面额有 1,2,…,109 且不限张数,但由于每枚硬币至少为 1,且总和为 s,最后一枚硬币最大只可能取到 s,所以上述状态和转移成立。
复杂度分析
- 时间复杂度:外层枚举
s=1..n,内层枚举t=1..k,再枚举最后一枚的面额x=1..s,总体 O(n2k)。 - 空间复杂度:使用二维表
dp,规模约为 (n+1)×(k+1),即 O(nk)。
代码实现
Python
# 题面功能放在外部函数里
def count_sequences(n, k):
# dp[s][t]:恰好用 t 枚硬币凑成和 s 的方案数
dp = [[0] * (k + 1) for _ in range(n + 1)]
dp[0][0] = 1 # 边界:0 枚硬币凑出 0 的方案为 1
# 逐步累加构造
for s in range(1, n + 1):
# t 不可能超过 s(至少每个硬币为 1)
for t in range(1, min(k, s) + 1):
total = 0
# 枚举最后一枚硬币面额 x
for x in range(1, s + 1):
total += dp[s - x][t - 1]
dp[s][t] = total
return dp[n][k]
if __name__ == "__main__":
# ACM 风格输入输出:一行两个整数
import sys
data = sys.stdin.read().strip().split()
n, k = map(int, data[:2])
ans = count_sequences(n, k)
print(ans)
Java
import java.io.BufferedInputStream;
import java.util.Scanner;
public class Main {
// 外部函数:计算恰好用 k 枚硬币凑成 n 的方案数(有序)
static long countSequences(int n, int k) {
// 使用 long,数据范围下 C(62,31) 约 4.7e18,可放入 long
long[][] dp = new long[n + 1][k + 1];
dp[0][0] = 1L; // 边界
for (int s = 1; s <= n; s++) {
int tMax = Math.min(k, s);
for (int t = 1; t <= tMax; t++) {
long total = 0L;
// 枚举最后一枚硬币的面额 x
for (int x = 1; x <= s; x++) {
total += dp[s - x][t - 1];
}
dp[s][t] = total;
}
}
return dp[n][k];
}
public static void main(String[] args) {
// ACM 风格输入输出
Scanner sc = new Scanner(new BufferedInputStream(System.in));
int n = sc.nextInt();
int k = sc.nextInt();
sc.close();
long ans = countSequences(n, k);
System.out.println(ans);
}
}
C++
#include <bits/stdc++.h>
using namespace std;
// 外部函数:计算恰好用 k 枚硬币凑成 n 的有序方案数
// 使用 unsigned long long 足以覆盖本题数据范围
unsigned long long count_sequences(int n, int k) {
vector<vector<unsigned long long>> dp(n + 1, vector<unsigned long long>(k + 1, 0ULL));
dp[0][0] = 1ULL; // 边界
for (int s = 1; s <= n; ++s) {
int tMax = min(k, s);
for (int t = 1; t <= tMax; ++t) {
unsigned long long total = 0ULL;
// 枚举最后一枚硬币面额 x
for (int x = 1; x <= s; ++x) {
total += dp[s - x][t - 1];
}
dp[s][t] = total;
}
}
return dp[n][k];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
if (!(cin >> n >> k)) return 0;
auto ans = count_sequences(n, k);
cout << ans << "\n";
return 0;
}
题面描述
给定两个正整数 n,k。你有面额为 1,2,3,…,109 的硬币,每种面额数量无限。你必须恰好选出 k 枚硬币,并且要求它们的总面额之和为 n。 选择的顺序不同视为不同方案(如 2,1 与 1,2 记为两种)。求满足条件的方案数;
输入输出
输入: 一行两个整数 n,k。
输出: 输出一个整数,表示恰好用 k 枚硬币凑成面额 n 的方案数。
数据范围
- 1≤n≤63
- 1≤k≤n
样例
输入
3 2
输出
2
说明
可行序列:1,2,2,1。
输入
4 3
输出
3
说明
可行序列:1,1,2,1,2,1,2,1,1。