B3635 硬币问题 題解

· · 题解

B3635 硬币问题 題解

管理员注：

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

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

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

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

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

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

首先，假设我们知道：

那么要凑 15 元的话：

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

所以，我们能得出：

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

这是一个 dp 的基本思路。

结论

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

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

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

\min (a + 1 , b + 1 , c + 1) + 1

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

表格法：

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

n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
f(n) 0 1 2 3 4 1 2 3 4 5 2 1 2 3 4 3

那么，代码实现就如下：

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

时间复杂度 O(n)。

我们总结一下：