自动搬运

查看原文

来自洛谷，原作者为

	ShanCreeperPro DILL QQTeam：746219450

搬运于2025-08-24 21:14:04，当前版本为作者最后更新于2022-07-01 14:29:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

B3635 硬币问题 題解

管理员注：

阅读本文章前，请先阅读$\ \texttt{ShanCreeper}$ B 题库题解的声明，并了解由于课程需要不展示代码。

如需系统学习相关知识点请报名【洛谷-基础算法计划】

究极无敌典中典之入门 dp 问题。

有面值 1 5 11 的三种硬币，问凑出 $n$ 元钱要多少枚硬币。

尝试贪心，尽可能先用大面额，不够再用小面额。

但这是错误的，例如凑 15 元，贪心方法是 $11+1+1+1$，而最优却是 $5+5+5$。

首先，假设我们知道：

• 凑14元至少要4枚硬币；
• 凑10元至少要2枚硬币；
• 凑4元至少要4枚硬币。

那么要凑 15 元的话：

• 先拿 1 元，还要 14 元，即总共要 5 枚；
• 先拿 5 元，还要 10 元，即总共要 3 枚；
• 先拿 11 元，还要 4 元，即总共要 5 枚。

所以，只要我们知道了凑 14,10,4 元需要多少硬币，我们不需要其他条件就能求出最少方案。

所以，我们能得出：

用小问题的解，求大问题的解。

这是一个 dp 的基本思路。

结论

要解决凑 $n$ 元的问题，需要知道以下数据：

代价：凑足 $n$ 元需要多少枚硬币：

• $n-1$ 的代价是 $a$，加上 1 元可以凑到 $n$；
• $n-5$ 的代价是 $b$，加上 5 元可以凑到 $n$；
• $n-11$ 的代价是 $c$，加上 11 元可以凑到 $n$。

所以，凑 $n$ 元的代价就是：

所以，求 $n$ 的问题我们可以分解成求 $n-1,n-5,n-11$ 这三个小问题，这个问题规模是在下降的。

表格法：

用 $f(n)$ 表示凑出 $n$ 元钱所需的硬币格数，按照刚才的方法，可以填出：

那么，代码实现就如下：

• 首先开 $f$ 数组，存储 $f(n)$ 的结果；

• $f_0$ 的初始值是 $0$ 哦；

• 从 1 到 $n$ 循环，其中 $f_i$ 的值为 $\min(f_{i-1},f_{i-5},f_{i-11})$。

• 注意，$f_{i-5}$ 和 $f_{i-11}$ 可能会越界。

当然，如果你觉得判断越界不好想的话，你可以把从 $f_0$ 到 $f_{11}$ 全部初始化（

时间复杂度 $O(n)$。

我们总结一下：

• dp 问题，发现只要解决几个更小规模的问题，就能得到大问题的解；
• 所以我们可以设计一张表格，每个格子代表一个问题的解；
• 根据初始信息，一步步填表格；
• 填完后，就得到了答案。