SOURCE

let dpTable = {};
function coinChange(coins, amount) {
    dp(coins, amount)
}

function dp(coins, amount) {
    if (amount < 0) 
        return -1;
    if (amount === 0) 
        return 0;
    if (!dpTable[amount]) {
        let num = amount+1;
        for(let index in coins) {
            let coin = coins[index];
            let subNum = dp(coins, amount - coin);
            if (subNum >= 0) {
                num = (num > (1+subNum) ? (1+subNum) : num);
            }
        }
        dpTable[amount] = num;
        console.log("amount " + amount + " needs " + num + " coins")
    }
    
    return dpTable[amount];
}

coinChange([1,2,5], 30)


// let num = 5, subNum = 3
// num = (num > (1+subNum) ? (1+subNum) : num);
// console.log(num)

let dpTablePre = {};
function coinChanges(coins, amount) {
    dpTablePre[0] = 0;
    dps(coins, amount)
}

function dps(coins, amount) {
    if (amount < 0) 
        return -1;
    if (amount === 0) 
        return 0;
    for (let i = 1; i <= amount; i ++) {
        for(let index in coins) {
            let coin = coins[index];
            if (i - coin >= 0) {
                if(!dpTablePre[i]) {
                    dpTablePre[i] = 1+dpTablePre[i - coin]
                } else {
                    dpTablePre[i] = (dpTablePre[i] > (1+dpTablePre[i - coin]) ? (1+dpTablePre[i - coin]) : dpTablePre[i]);
                }
            }
        }
        console.log("amount " + i + " needs " + dpTablePre[i] + " coins")
    }
    
    
    return dpTablePre[amount];
}

coinChanges([1,2,5], 30)