algorithm - 动态规划 : the smallest number of coins to make change for 65 cents

Question

我正在尝试使用动态规划解决问题，问题如下:

给定无限供应的硬币(便士、镍币、角钱、双角钱、四分之一)值(1、5、10、20、25)，请找到最少数量的硬币找零 65 美分。使用什么硬币(以及每种硬币数量)？说明使用动态规划算法以及如何获得使用的硬币。

请注意，我不希望任何人为我说明整个表格，但我对如何为这个问题填写表格有点困惑。

我知道我的 table 看起来有点像这样:

    5   10  15  20  25  30  35  40  45  50  55  60  65
1

5

10

20

25

(我省略了 1，因为我知道这不是最佳解决方案)我最初的想法是表格会像这样填写:

    5   10   15  20  25  30  35  40  45  50  55  60  65
1

5   1    2   4   5    5   6  7   8    9  10  11  12  13

10  0    1   

20

25

当我必须走得更远时，我会被困在这里。我不认为我完全理解动态编程如何解决这个问题。我一直在阅读我的书和在线阅读，但我仍然有点困惑。

编辑:

感谢其中一个答案，这就是我制定解决方案的方式:

    5     10    15    20    25    30    35    40    45    50    55    60    65
1   

5   1           1                  1                             1           

10         1    1                       1                              1     

20                    1                       2     1                        2

25                          1      1    1           1      2     2     2     1

Answer 1

你做错了。列代表您必须归还的总零钱，行单元格代表使用的某些硬币(便士、镍币、10 美分、20 美分、25 美分)的数量。

该算法的重点是返回最少数量的硬币。例如，如果零钱是 25，您应该退还一个季度，而不是 25 便士。您可以看到我在下表中使用四分之一作为 25 美分列。

在您的 15 零钱列中的示例中，您使用的是 4 x 5 美分，这是次优的，因为您可以使用一枚 10 美分的硬币和一枚 5 美分的硬币来返回总共 15。在 20 美分的列中您使用的是 5 x 5 美分找零，这是不正确的，而且也不是最优的，因为您本可以使用一枚 20 美分的硬币来返还 20 美分。

这是为前 5 列填充的表格。您可以填写其余部分:

    5   10   15  20  25  30  35  40  45  50  55  60  65
1

5   1        1     

10      1    1  

20               1

25                   1
--------------------------------------------------------
T   1   1    2   1   1

我在底部添加了一个 T 行来计算您用作零钱的硬币总数。你的目标是拥有最少的。此行中每一列的可能数量。