DAY9 - Dynamic Programming - Coin Change Solution

coinChange.js

// top-down approach
const memo = {};
function coinChange(n) {
    // base case
    if (n <= 0) return Number.MAX_VALUE;
    if (n === 1 || n === 3 || n === 4) return 1;
    // induction case
    if (memo[n]) return memo[n];
    memo[n] = Math.min(...[coinChange(n-1),
        coinChange(n-3),
        coinChange(n-4)]) + 1;
    return memo[n];
}

// bottom-up approach
function coinChange(n) {
    const memo = {};
    // base case
    memo[1] = memo[3] = memo[4] = 1;
    memo[2] = 2;
    // induction case
    for (let i = 5; i <= n; i++) {
        memo[i] = Math.min(...[memo[i-1], memo[i-3], memo[i-4]]) + 1;
    }
    return memo[n];
}