Making-Change problem with Dynamic Programming

Description

// We write the problem as a table.  Each row represents the amount of change to make,
// and the value at each column represents the highest coin we're allowed to use 
// in making that amount of change
// That is to say, in row 5, col 2 is the number of ways to make 5 cents, using only the two lowest coins.
 
// To calculate the value of each square, we add the values of two other squares together -
//    * The square to the left, which represents all possibilites using smaller coins.
//    * The square as many rows above as the value of that coin.
//      This is all possibilities after taking away one of this coin
// This method avoids having to ever call things recursively - we just build a big table!
// The first row is all we need to start things off, and we set it to 0 and then all 1s.
 
// Example: if coin values are 1, 2, and 4:
 
// coins:  0,  1,  2,  4
// --------------------
// 0:      0   1   1   1
// 1:      0   1   1   1
// 2:      0   1   2   2
// 3:      0   1   2   2
// 4:      0   1   3   4
// 5:      0   1   3   4
// 6:      0   1   4   6
// ...
// We continue to exapand this table until we get to the row we want.  The answer is in the bottom right.
 

Solution

var coinValues = [10000, 5000, 2000, 1000, 500, 100, 50, 25, 10, 5, 1];

var makeChange = function(amount) {
  var coins = coinValues.slice().reverse();
  var coinsLength = coins.length;
 
  var cache = [[]];
  for (var i = 0; i < coinsLength; i++) {
    cache[0].push(1);
  }
 
  for (var row = 1; row <= amount; row++) {
    cache[row] = [];
    for (var col = 0; col < coinsLength; col++) {
      var left = col > 0 ? cache[row][col-1] : 0;
      var above = row - coins[col] >= 0 ? cache[row - coins[col]][col] : 0;
      cache[row][col] = left + above;
    }
  }
  return cache[amount][coinsLength - 1];
};