我会考虑一次一次归纳地构建解决方案：

可用的硬币有1c，5c，10c，25c（您可以根据需要进行调整）

1. 1c的最小硬币= 1 X 1c。最多4美分，我们需要1c硬币，因为这是最小的面额。
2. 5美分，我们有一枚5c硬币。结合上面的4c，我们可以生成1到9之间的任何数字。
3. 对于10美分，我们需要1 X 10c。结合以上三个，我们可以生成1到19之间的任何数字。
4. 对于20c，我们需要2 x 10c，因为20可被10整除。

如果您可以归纳地解决问题，则可能更容易解决。

编辑：
好的，这是另一种尝试解释动态编程解决方案的尝试：

考虑一下一个具有x行（x是不同面额的数量）和n列（n是您必须使用最小面额来构建的数量）的表。该表中的每个单元格都代表一个不同的子问题，并将最终包含该问题的解决方案。承担：

第1行代表集合，{1c}即在第1行中允许您使用无限。1c
第2行代表集合，{1c, 10c}即在第2行中您可以使用无限，1c而10c
第3行代表集合{1c, 10c, 15c}，以此类推…
每列代表您要构造的数量。

因此，每个单元对应一个小子问题。例如（索引是从1开始为简单起见）
cell(1, 5)==>构造5c只使用{1c}
cell(2, 9)==>构造9c使用{1c, 10c}
cell(3, 27)==>构造27c使用{1c, 10c, 15c}
现在你的目标是获得答案cell(x, n)

Solution:
从最简单的问题开始解决表格。解决第一行很简单，因为在第一行中唯一可用的面额是{1c}。第1行中的每个单元格都有一个平凡的解，导致cell(1, n)= = {nx1c}（的n硬币1c）。

现在进入下一行。概括第二行，让我们看看如何求解（说），cell(2, 28)即28c使用构造{1c, 10c}。在这里，您需要确定是否包含10c在解决方案中，以及多少枚硬币。您有3个选择（3 = 28/10 + 1）

Choice 1：从上一行（存储在中）中
取出{1x10c}其余部分cell(1, 18)。这给你{1x10c, 18x1c}=19 coins

Choice 2：从上一行（存储在中）中
取出{2x10c}其余部分cell(1, 8)。这给你{2x10c, 8x1c}=10 coins

Choice 3：从上一行（存储在中）中
取出no 10c和其余的行cell(1, 28)。这给你{28x1c}=28 coins

显然，选择2是最好的选择，因为它需要更少的硬币。将其写下表中并继续。表格将一次填充一行，并在一行中以数量递增的顺序填充。

按照上述规则，您将到达cell(x, n)，解决方案是在n/p + 1其他选择之间进行选择，其中p=
row中的最新面额x。最佳选择是您的答案。

该表实际上记录了较小问题的解决方案，因此您无需一次又一次地解决它们。