## 322. Coin Change

###### tags: `Dynamic Programming` `Medium`

>[322. Coin Change](https://leetcode.com/problems/coin-change/description/l)

<br>

:::info
:::spoiler *Optimal Space & Time Complexity*
<br>

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

:::

<br>

## Thoughts & Solutions

### YC
:::spoiler Code

:::

<hr/>

### Sol
:::spoiler Code

:::

<hr/>

### 東

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

:::spoiler 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];
};

:::

<hr/>

### Jessie

:::spoiler Code

:::

<hr/>

### Howard

:::spoiler Code

:::

<hr/>

### Haoyu

:::spoiler Code

#### Try 1: Enumerate

#### Try 2
[贾考博 LeetCode 322. Coin Change - 无限金钱!](https://www.youtube.com/watch?v=aQhNCYN5TsU)

/**
 * @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];
};

:::

<hr/>

<br>

## Live Coding

:::spoiler (name)

// write your code here

:::