algorithm - 动态规划求最小硬币数

Question

作为我的 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 的最小硬币数量。

Answer 1

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) } 实际上是在选择“什么是最好的”详尽无遗:

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

取其中的最小值可以确保我们(因为它已穷尽所有可能性)c(i,j) 是最小值。