algorithm - +1 在硬币找零问题(动态规划方法)的递归关系中意味着什么？

Question

我看到了 Coin Change 问题。一般来说，输入是 n(要返回的零钱)和可用的面额(以美分计的硬币值(value))，v₁ < v ₂ < v₁ < ... < v_k;目标是用最少的硬币找零 n 美分。

我正在阅读 this pdf来自哥伦比亚大学，但我不明白为什么在第 6 号幻灯片中，我们在递归关系中有一个 +1:

是否代表我们已经使用过的币种？

Answer 1

C[p]指示您从可用硬币数组 d 中构建面额 p 的最少硬币数量。

因此，要创建这样的金额，您必须选择硬币 d[i]这样 d[i]<p .

假设您从 d 中选择了一枚硬币 d[i]。这意味着您的硬币数量现在是一个。

现在为了总和 p，收集更多硬币以获得总和 p-d[i] .

但是您已经有了计算总和所需的 min_coins p-d[i]在C[p-d[i]] .

这意味着产生总和 p 的一种可能的硬币数量是 1+C[p-d[i]] .

但是 d[i]<p 可能有多个面额可能的话，那么你必须选择一个对你的影响最小的那个，这正是你的功能正在做的事情。

这样你就可以理解+1作为我们正在考虑用于求和的第一个硬币的功能 p .