Coins - CtCI 8.11

Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents) and pennies (1 cent), write code to calculate the number of ways of representing n cents.

by Hari Menon

JavaScript

function initializeArray(count, numericValue) {
    return Array.apply(null, Array(count)).map(Number.prototype.valueOf, numericValue);
}

function makeChange(amount, coins, index, map) {
    if (map[amount][index] > 0) {
        return map[amount][index];
    }
    if (index >= coins.length - 1) {
        return 1;
    }
    var coin = coins[index];
    var ways = 0;
    for (var i = 0; i * coin <= amount; i++) {
        var amountRemaining = amount - i * coin;
        ways += makeChange(amountRemaining, coins, index + 1, map);
    }
    map[amount][index] = ways;
    return ways;
}

function makeChangeInit(n) {
    var coins = [25, 10, 5, 1];
    var cache = new Array(n + 1);
    for (var i = 0, len = cache.length; i <= n; i++) {
        cache[i] = initializeArray(coins.length, 0);
    };
    console.log(makeChange(n, coins, 0, cache));
    // console.log(cache.join('\n'));
}

makeChangeInit(10);