javascript制作更改算法

Question

我正在用 javascript 解决这个“做出改变”的问题:

问题:

Given an amount of money, an array of coin denominations, compute the number of ways to make the amount of money with coins of the available denominations.

Example:

For amount=4 (4¢) and denominations=[1,2,3] (1¢, 2¢ and 3¢), your program would output 4—the number of ways to make 4¢ with those denominations:

1¢, 1¢, 1¢, 1¢

1¢, 1¢, 2¢

1¢, 3¢

2¢, 2¢

我找到了一个解决方案:

var makeChange = function(total){
  var count = 0;
  var coins = [1, 2, 5, 10, 20, 50, 100, 200];

  var changer = function(index, value){

    var currentCoin = coins[index];

    if( index === 0){
      if( value % currentCoin === 0){
        count++;
      }
      return;
    }

    while( value >= 0 ){
      changer(index-1, value);
      value -= currentCoin;
    }
  }
  changer(coins.length-1, total);
  return count;
};

makeChange(200);

问题:

1. 有人可以向我解释发生了什么事吗？我尝试按照代码进行操作，但在递归之间迷失了方向。

我知道他正在计算最终的硬币值(value)，并且他正在从给定的总数中减去。 (但为什么呢？)我有点迷路了。

1. 当while循环中value >= 0时，它一直在循环增加索引，我不明白为什么。

有人能理解这个算法吗？

抱歉，刚开始学习动态规划。

谢谢，

Answer 1

让我们跟踪 makeChange(4) 发生了什么:

函数 changer 被定义然后被第一次调用。

value = 4, index = 7, coins[7] = 200

由于变量 index 不为 0，我们继续进行 while 循环。

第二次调用 changer 是用 index 6

Meanwhile, the first call continues the 'while'
loop but since 200 has been subtracted from 'value',
'value' is now less than 0 so the 'while' loop terminates
and this first call does nothing more.

(Keep in mind that the variable 'value' is distinct 
and private to each call, so the 'while' loop only 
affects the 'value' in its own function call.)

好的，现在这个模式继续所有函数调用，index 指向大于 value 的硬币，直到 index 为 1。

value = 4, index = 1, coins[1] = 2 

这次更多的发生在 while 循环中:

We get the function call, 'changer(0,4)', 
AND a second function call, 'changer(0,2)', 
after we subtract 2 from 'value', which was 4,
AND a third function call, 'changer(0,0)', 
after we subtract 2 from 'value', which was 2.

These 3 calls respectively represent:

   1 + 1 + 1 + 1
   2 + 1 + 1
   2 + 2

Each time the line 'value -= currentCoin' is executed,
it represents the start of another set of choices for 
solutions that include that coin.

4 % coins[0] = 0, meaning 4 is divisible by 1 represents 1 + 1 + 1 + 1

4 - 2 folllowed by 2 % 1 represents 2 + 1 + 1

and 4 - 2 - 2 represents 2 + 2

总计数:3