Problem J28: Coin Exchange / 纸币换硬币

版权信息： · 数学递推与完全背包问题基础题

任务总览

题目描述

国王希望了解换币的组合方式。

他手中有一张面额为 $n$ 元的纸币（注意单位是​ 元 ​），需要将其换成如下三种​ 硬币 ​：

• 1 分（0.01 元）
• 2 分（0.02 元）
• 5 分（0.05 元）

每种硬币至少要有一枚。

请你编程计算，将 $n$ 元纸币换成这些硬币，一共有多少种不同的组合方式。

输入格式

一个正整数 $n$（$1 \leq n \leq 100$），表示纸币面额（单位为元）。

输出格式

输出一个整数，表示满足条件的换法总数。

输入输出样例

输入示例

1

输出示例

461

题目分析与解法

这是一个典型的 完全背包 + 限制条件 问题。

✅ 思路：

• 将 $n$ 元转化为 ​ 整数分数 ​（如：$1 元 = 100 分$）；
• 用三种硬币 ${ 1, 2, 5 }$ 枚举组合使得它们之和等于 $100$；
• 每种硬币至少出现一次；
• 相当于求满足：a * 1 + b * 2 + c * 5 = 100 且 $a, b, c geq 1$ 的整数解个数。

✅ 枚举法可行：

• 枚举 $c$（5 分硬币数量），最多
• 枚举 $b$（2 分硬币数量）；
• 计算 $a = 100 - 5c - 2b$，判断是否 $\geq 1$ 且为整数。

时间复杂度分析