322. Coin Change

tags: Dynamic Programming Medium

322. Coin Change

Optimal Space & Time Complexity

- Time complexity: O()
- Space complexity: O()

Thoughts & Solutions

YC

Code

---

Sol

Code

---

東

dp(n) = min of 
            dp(amount - coins[0]) + 1, while dp(amount - coins[0]) !== -1
            dp(amount - coins[1]) + 1, while dp(amount - coins[1]) !== -1
            ...
            dp(amount - coins[i]) + 1, while dp(amount - coins[i]) !== -1

dp 直接填入 Infinity 會簡化 Code

Code

// Time O(m*n) | Space O(n) - m is number of coins, n is amount
var coinChange = function(coins, amount) {
    const dp = new Array(amount + 1).fill(0);
    dp[0] = 0;

    for(let n = 1; n <= amount; n++) {
        let minCoinAmount = Infinity;
        for(let i = 0; i < coins.length; i++) {
            if(n - coins[i] < 0 && dp[n - coins[i]] === -1) {
                continue;
            } ;
            if(dp[n - coins[i]] + 1 < minCoinAmount) {
                minCoinAmount = dp[n - coins[i]] + 1;
            }
        }

        if(minCoinAmount === Infinity) {
            dp[n] = -1;
        } else {
            dp[n] = minCoinAmount;
        }
    }

    return dp[amount];
};

---

Jessie

Code

---

Howard

Code

---

Haoyu

Code

Try 1: Enumerate

Try 2

贾考博 LeetCode 322. Coin Change - 无限金钱!

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function(coins, amount) {
    const dp = new Array(amount + 1).fill(Infinity);

    dp[0] = 0;

    for (i = 1; i <= amount; i += 1) {
        for (const coin of coins) {
            if (i - coin >= 0 && dp[i - coin] !== Infinity) {
                dp[i] = Math.min(dp[i - coin] + 1, dp[i]);
            }
        }
    }

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

---

Live Coding

(name)

// write your code here