algorithm - 硬币找零问题中递归关系背后的原因是什么？

Question

我知道如何在硬币找零问题中使用递归关系（从给定的一组硬币中获得总和 S 的方法总数），但是，我不明白它来自哪里。我在互联网上搜索了它，据我记得他们抛出了这个事实（recurrence r/ship），然后他们继续实施它。有人可以解释一下吗？

10{1,2,3,4} = 10{1,2,3} + 6{1,2,3,4}

上面的等式只是一个例子。换句话说，这意味着使用硬币 {1,2,3,4} 制作 10 的方式总数等于使用 {1,2,3} 制作 10 的方式总数 puls 制作方式的总数6 使用硬币{1,2,3,4}。

标签： algorithmmathstatisticsdynamic-programmingprobability

Answer 1

当您需要计算获得总和的可能性时，您应该考虑不使用某个硬币的可能性，以及您确实使用它的可能性（至少一次）。当您知道第一种情况和第二种情况的可能性数量时，您就会知道答案：它是这两者的总和。

所以，现在问题变成了，我如何计算这两种不同情况下的可能性数量？

在第一种情况下，您简化了问题，因为您排除了一种硬币类型，从而减少了您仍然可以选择的不同种类硬币的数量。

在第二种情况下，您减少了剩余的金额以支付，因为您已经拿走了硬币。这也减少了问题：不是在可用硬币方面，而是在总和的数量方面。

无论哪种情况，您都可以将相同的算法应用于简化问题。这就是递归的用武之地：那些减少的问题将再次分裂成你是否使用硬币的情况，......等等。

最终问题将大大减少，以至于您可以轻松知道它的可能性计数：

• 如果剩余金额为零：这正是我们的目标：将导致这一点的硬币选择视为有效可能性，并返回 1。

• 如果剩余金额为负数，那么您显然使用了太大的硬币，您不应将此视为有效：返回 0 作为可能性计数。

• 如果剩余数量是严格正数，并且没有硬币剩下：显然我们丢弃了最后一种剩余的硬币。情况不妙。我们不能把这算作一种可能性，所以返回 0

这些计数（0 或 1）将在递归树中冒泡，您将在其中将它们加在一起。该总和将依次返回到递归树的更深处，直到最终所有可能性都被加起来。