518.Coin Change II
===

###### tags: `Medium`,`Array`,`DP`

[518. Coin Change II](https://leetcode.com/problems/coin-change-ii/)

### 題目描述

You are given an integer array `coins` representing coins of different denominations and an integer `amount` representing a total amount of money.

Return *the number of combinations that make up that amount.* If that amount of money cannot be made up by any combination of the coins, return `0`.

You may assume that you have an infinite number of each kind of coin.

The answer is **guaranteed** to fit into a signed **32-bit** integer.

### 範例

**Example 1:**

Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

**Example 2:**

Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.

**Example 3:**

Input: amount = 10, coins = [10]
Output: 1

**Constraints**:

* 1 <= `coins.length` <= 300
* 1 <= `coins[i]` <= 5000
* All the values of `coins` are **unique**.
* 0 <= `amount` <= 5000

### 解答

#### TypeScript

function change(amount: number, coins: number[]): number {
  const dp: number[] = new Array(amount + 1).fill(0);
  dp[0] = 1;

  for (const coin of coins) {
    for (let i = coin; i <= amount; i++) {
      dp[i] += dp[i - coin];
    }
  }

  return dp[amount];
}

> 思路：DP
> 1. 建立一個 DP table, `dp[i]` 代表組成 `i` 元的組合數
> 2. `dp[0] = 1`, 代表組成 0 元的組合數為 1 (都不選)
> 3. `dp[i - coin]` 代表組成 `i - coin` 元的組合數，因為當我們在湊出 `i - coin` 的組合數基礎上，再加上 `coin` 就可以湊出 `i` 元的一種新組合
> 以 coins = [1, 2], amount = 3 為例：
> dp[0] = 1 => []
> dp[1] = dp[1 - 1] = 1 => [1]
> dp[2] = dp[2 - 1] + dp[2 - 2] = 2 => [1, 1], [2]
> dp[3] = dp[3 - 1] + dp[3 - 2] = 3 => [1, 1, 1], [1, 2], [2, 1]
> 4. 遍歷 coins，並從 coin 開始遍歷 dp，直到 amount，然後更新 `dp[i]` 把每種 `dp[i - coin]` 的組合數加上去
> 5. 回傳 `dp[amount]`
> [name=Sheep][time=Fri, Aug 11, 2023]

#### C++

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        ios_base::sync_with_stdio(0); cin.tie(0);

        int numCoins = coins.size();
        vector<int> dp(amount + 1, 0);
        dp[0] = 1;
        for (const int coin : coins) {
            for (int currHold = coin; currHold <= amount; currHold ++) {
                dp[currHold] += dp[currHold - coin];
            }
        }
        return dp[amount];
    }
};

> [name=Jerry Wu][time=11 August, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)