0

我对硬币问题的动态编程技术的矩阵应该是什么样子感到困惑。假设我有 1c、5c、10c 和 25c 的面额，我称之为 make-change(10)。即我想为 10 美分进行更改，我的最终矩阵/数组应该是什么样子。我需要知道这一点，因为我想在程序的开头分配一个数组。我不是在这里寻找代码。

4

2 回答 2

2

您可以使用一个矩阵，其中一个维度显示您现在正在计算的总和，另一个显示您可以使用哪些硬币 - 例如，第一行显示仅使用 1c 硬币获得给定总和的方法数量，第二行 - 1c 和 5c，第三行 - 1c、5c 和 10c 等等。

因此，在您的示例中，它可能如下所示：

Sum:  0 1 2 3 4 5 6 7 8 9 10
Ways: 1 1 1 1 1 1 1 1 1 1 1   (using only 1c coins - N x 1c)
      1 1 1 1 1 2 2 2 2 2 3   (using 1c and 5c coins - either Nx1c, 1x5c + (N - 5)*1c or 2x5c)
      1 1 1 1 1 2 2 2 2 2 4   (using 1c, 5c and 10c coins - one of the above, or 1x10c)

不过，您实际上并不需要存储整个矩阵 - 最后一行应该总是足够的。

摆脱大部分矩阵的解释：

假设您在仅使用 1c 硬币时找到了答案（这并不是一件非常困难的事情），并且它存储在单个数组中，例如DP. 现在，您有了这些信息，并且想知道 1c 和 5c 硬币的答案。

您可以从 开始sum = 0 to 10，保持以下不变量：

  • 当您计算 的答案时，从 0 到包含0的每个数字sum的条目显示使用 1c 和 5c 硬币的方法数。仅使用 1c 硬币时，所有其余条目（从数组末尾到数组末尾）都包含答案。DPxsum - 1sumsum

并且维护它实际上非常容易：当您计算 的答案时x，您知道：

  • x仅使用 1c 硬币的方法数量- 这是DP[x]，因为我们还没有覆盖它；
  • x使用至少一个 5c 硬币的方法数 - 即，DP[x - 5]即在我们移除 5c 后获得剩余硬币数量的方法数（或 0，如果x - 5 < 0）。

然后您可以将这两个数字相加并将结果存储在DP[x]. 然后继续类似地处理其余的硬币。

于 2012-10-02T21:20:02.057 回答
0

我认为一个将金额映射到硬币列表的哈希图。所以它看起来像：

{0 => (),
 1 => (1),
 2 => (1,1),
 3 => (1,1,1),
 ...
 13 => (10,1,1,1)
 ...
}
于 2012-10-02T20:33:13.800 回答