硬币找零问题中递归关系背后的原因是什么？
What is the reasoning behind the recurrence relationship in the coin change problem?
我知道如何在硬币找零问题中使用递归关系（从给定的一组硬币中获得总和 S 的方法总数），但是，我不明白它是从哪里来的。我在互联网上搜索了它，据我所知，他们提出了这个事实（重复 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 的方法总数6 使用硬币{1,2,3,4}.
当你需要计算得到总和的可能性时，你应该考虑你不使用某种硬币的可能性，以及你的可能性do 使用它（至少一次）。当您知道第一种情况和第二种情况的可能性数量时，您就会知道答案：它是这两者的总和。
那么，现在的问题是，我如何计算这两种不同情况下的可能性数量？
在第一种情况下，你简化了问题，因为你排除了一种硬币类型，减少了你仍然可以选择的不同种类硬币的数量。
在第二种情况下，你减少了剩余的金额来支付，因为你已经拿走了硬币。这也减少了问题：不是在可用硬币方面，而是在总计金额方面。
在任何一种情况下，您都可以将相同的算法应用于简化的问题。这就是递归的用武之地：那些减少的问题将再次分成你是否使用硬币的情况，...等等
最终问题会大大减少，你可以很容易地知道它的可能性：
如果剩余金额为零：这正是我们的目标：将导致这一点的硬币选择视为有效的可能性，并且return 1.
如果剩余金额为负数，那么你显然使用了太大的硬币，你不应该将其视为有效：return 0 作为可能性的计数。
如果剩余数量严格为正数，和没有硬币剩余：显然我们丢弃了最后一种剩余的硬币。这个不好。我们不能认为这是一种可能性，所以 return 0
这些计数（0 或 1）将在递归树中冒泡，您可以在递归树中将它们相加。该总和还将 return 在递归树中更上一层楼，直到最终所有可能性都被加起来。
我知道如何在硬币找零问题中使用递归关系（从给定的一组硬币中获得总和 S 的方法总数），但是，我不明白它是从哪里来的。我在互联网上搜索了它，据我所知，他们提出了这个事实（重复 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 的方法总数6 使用硬币{1,2,3,4}.
当你需要计算得到总和的可能性时，你应该考虑你不使用某种硬币的可能性，以及你的可能性do 使用它（至少一次）。当您知道第一种情况和第二种情况的可能性数量时，您就会知道答案：它是这两者的总和。
那么，现在的问题是，我如何计算这两种不同情况下的可能性数量？
在第一种情况下，你简化了问题，因为你排除了一种硬币类型，减少了你仍然可以选择的不同种类硬币的数量。
在第二种情况下，你减少了剩余的金额来支付，因为你已经拿走了硬币。这也减少了问题：不是在可用硬币方面，而是在总计金额方面。
在任何一种情况下，您都可以将相同的算法应用于简化的问题。这就是递归的用武之地：那些减少的问题将再次分成你是否使用硬币的情况，...等等
最终问题会大大减少，你可以很容易地知道它的可能性：
如果剩余金额为零：这正是我们的目标：将导致这一点的硬币选择视为有效的可能性，并且return 1.
如果剩余金额为负数，那么你显然使用了太大的硬币，你不应该将其视为有效：return 0 作为可能性的计数。
如果剩余数量严格为正数，和没有硬币剩余：显然我们丢弃了最后一种剩余的硬币。这个不好。我们不能认为这是一种可能性，所以 return 0
这些计数（0 或 1）将在递归树中冒泡，您可以在递归树中将它们相加。该总和还将 return 在递归树中更上一层楼，直到最终所有可能性都被加起来。