algorithm - 动态编程以找到最小数量的硬币

Question

我试图理解我的硬件问题的一部分，但它看起来真的像中文......

假设我们有硬币x_1, x_2, x_3, ... x_n。 x_1 = 1总是。我们希望以最少数量的硬币提供一定数量的钱。然后我们使用动态规划。

现在我不明白这一点 - 返回金额的最小硬币数量c(i,j) = min { c(i-1,j), 1+c(i,j-x_i) } 在哪里。c(i,j)j

Answer 1

c(i,j-x_i)j-x_i是仅使用硬币来获得价值的最小硬币数量i,i+1,...,n（这是归纳假设，这就是递归公式向我们保证的）。
因此，使用给定的一组硬币 + 一个额外的硬币 value1+c(i,j-x_i)的最小方法是我们决定使用它。j-x_ix_i

由此，c(i,j) = min { c(i-1,j), 1+c(i,j-x_i) }实际上是在穷举地选择“什么是最好的”：

1. 取当前硬币，并递归检查其余较小的问题
2. 决定不接受它 - 再次递归检查较小的问题。

取其中的最小值确保我们（因为它是详尽地完成的 - 在所有可能性上）c(i,j)是最小的。