【LeetCode】 518. Coin Change 2

Description

You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.

Note:
You can assume that

• 0 <= amount <= 5000
• 1 <= coin <= 5000
• the number of coins is less than 500
• the answer is guaranteed to fit into signed 32-bit integer

給予你不同面額的金幣和一個金額的總數。寫一個函式去計算有幾種組合可以湊成該金額。你可以假設每種面額的金幣都有無限枚。

提示：
你可以假設

• 0 <= amount <= 5000
• 1 <= coin <= 5000
• 金幣的種類數少於 500
• 答案保證可以用 32 位元的有號正整數去表示

Example:

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

Solution

• 一開始想到的是貪婪法，概念是一直拿硬幣，如果剛好拿滿就讓答案加一；拿超過就換下一種硬幣。

class Solution {
public:
    void greedy(int amount, vector<int> coins, int& ans)
    {
        if(amount == 0) ans++;
        if(coins.empty()) return;
        else if(amount > 0)
        {
            greedy(amount - coins.front(), coins, ans);
            coins.erase(coins.begin());
            greedy(amount, coins, ans);
        }
    }
    int change(int amount, vector<int>& coins) {
        int ans = 0;
        greedy(amount, coins, ans);
        return ans;
    }
};

• 結果吃了TLE，當金錢總數越大時這個演算法會跑超級久(基本上每一種組合都拿過一次，太過耗時)。

---

• 接著想到使用DP來加速。
• 總共產生0 ~ amount共amount + 1個格子，其代表金額為i的時候有的組合數。
  • 因此答案就是DP[amount]。
• 初始設定DP[0] = 1。(每種硬幣都不拿、一種組合)。
• 接著跑每一種硬幣，去更新 DP 即可。

Code

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount + 1, 0);
        dp[0] = 1;
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
    }
};

tags: LeetCode C++