322. Coin Change

Coin Change - LeetCodeLeetCode

time: O(n x c), n: amount, c: num of coins

space: O(n),

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function(coins, amount) {
    
    const sums = new Array(amount + 1).fill(Infinity);
    sums[0] = 0;
    for (let i = 0; i <= amount; i++) {
        for (let j = 0; j < coins.length; j++) {
            coin = coins[j];
            if (i - coin < 0) continue;
            sums[i] = Math.min(sums[i], sums[i - coin] + 1);
        }
    }

    return sums[amount] === Infinity ? -1 : sums[amount];
};