algorithm - 递归在换币算法中是如何展开的？

Question

我知道有大量的社论和博客解释这一点，但有一个共同点让我感到困惑。

考虑下面给出的递归:

coin_change(coins,i,N) = coin_change(coins,i-1,N) + coin_change(coins,i-1,N-val[i])

现在这看起来很简单，我认为我们要么排除硬币，要么包括它并解决剩余金额的问题。

但我的疑问是，既然有无限供应的硬币，我们可以取尽可能多的硬币来达到总和，那么我们如何将那个东西合并到递归解决方案中呢？

我也无法理解这个问题的基本情况!

Answer 1

这将创建一个二叉树，其中右分支一次又一次地搜索减去相同的硬币，左分支搜索所有其他硬币。

以 N = 3 和硬币 = {1, 2} 的简单情况为例:
右边的分支是:

{1,2}: 1->1->1  (1,1,1)
  {2}:  ->2     (1,2)

左边的分支是:

{2}:    2->X    (No solution)

如果 2 是第一个硬币，将给出相同的结果:
右手分支:

{2,1}: 2->X     (No solution)
  {1}   ->1     (2,1)

左手分支:

{1}:   1->1->1  (1,1,1)

注意 1:你不应该在第二次调用时有 -1:

coin_change(coins,i,N) = coin_change(coins,i-1,N) + coin_change(coins,i,N-val[i])

注2:这不是动态规划。