完全背包计数：f[j] 表示凑成 j 元方案数，f[0]=1，按 10/20/50/100 正序滚动 f[j]+=f[j-price]；n=0 输出 0。
OJ: roj
题目 ID: 1293
难度:入门
标签:动态规划背包问题完全背包计数DP
创建: 2026-09-30 03:41
更新: 2026-10-05 08:17
题目描述
小明有 n 元全部用来买书，书价为 10、20、50、100 元，每种可买多本，求恰好花完 n 元的方案数。输入一个整数 n（0 ≤ n ≤ 1000），输出方案种数；n=0 时按题目约定输出 0。样例：输入 20，输出 2；输入 15 或 0，输出 0。
思路
把买书方案看成完全背包计数：f[j] 表示凑成 j 元的方案数，f[0]=1，按 10/20/50/100 四种书价正序滚动 f[j] += f[j-price]。n=0 输出 0，否则输出 f[n]。
参考代码
Python 版：
python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 03:41
# update_at: 2026-09-30 03:41
import sys
PRICES = (10, 20, 50, 100) # 四种书价，即完全背包的物品体积
def count_plans(n: int) -> int:
"""恰好花 n 元的买书方案数：f[j] 表示恰好凑出 j 元的方式数。"""
f = [1] + [0] * n # f[0] = 1：一种书都不选也是"凑出 0 元"的初始状态
for price in PRICES:
for money in range(price, n + 1): # 正序扫：同一本书可重复购买
f[money] += f[money - price]
return f[n]
def solve() -> None:
n = int(sys.stdin.buffer.read())
# 样例规定 n = 0 时答案为 0：钱数非 10 的倍数时 f[n] 自然为 0，无需特判
print(count_plans(n) if n > 0 else 0)
if __name__ == "__main__":
solve()C++ 版（同一算法）：
cpp
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-05 08:18
* update_at: 2026-10-05 08:18
*/
#include <iostream>
using namespace std;
typedef long long ll;
const int MAXN = 1005;
ll f[MAXN]; // f[j] 表示恰好凑出 j 元的方案数
int price[4] = {10, 20, 50, 100};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
f[0] = 1; // 凑出 0 元有一种空方案
for (int i = 0; i < 4; i++) {
for (int j = price[i]; j <= n; j++) {
f[j] += f[j - price[i]];
}
}
// 题目约定 n=0 时输出 0（空方案不计入）
if (n == 0) cout << 0 << "\n";
else cout << f[n] << "\n";
return 0;
}