作为我的 HW，我正在尝试理解我的问题的一部分，但它看起来真的很像中文......
假设我们有硬币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 的最小硬币数量。
最佳答案
c(i,j-x_i) 是获得值 j-x_i 的最少硬币数量，仅使用硬币 i,i+1, ...,n(这是归纳假设，这就是递归公式向我们保证的)。
因此，1+c(i,j-x_i) 是获得 j-x_i 的最小方法，其中包含给定的一组硬币 + 一个额外的硬币值x_i，我们决定使用它。
据此，c(i,j) = min { c(i-1,j), 1+c(i,j-x_i) } 实际上是在选择“什么是最好的”详尽无遗:
- 获取当前硬币，并递归检查其余的较小问题
- 决定不接受它 - 然后再次递归地检查较小的问题。
取其中的最小值可以确保我们(因为它已穷尽所有可能性)c(i,j) 是最小值。
关于algorithm - 动态规划求最小硬币数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13273847/