Skip to content

Instantly share code, notes, and snippets.

@peterkhayes
Created May 20, 2014 07:34
Show Gist options
  • Save peterkhayes/37ebf77a19a787599f36 to your computer and use it in GitHub Desktop.
Save peterkhayes/37ebf77a19a787599f36 to your computer and use it in GitHub Desktop.
Making-Change problem with Dynamic Programming
// 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.
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];
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment