Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C++ - 518. Coin Change II

---

參考資訊：
https://github.com/doocs/leetcode/blob/main/solution/0500-0599/0518.Coin%20Change%20II/README_EN.md

題目：


方法：

          0 1 2 3 4 5
0 coins   1 0 0 0 0 0
1 (1)     1 1 1 1 1 1
2 (1,2)   1 1 2 2 3 3
3 (1,2,5) 1 1 2 2 3 4

解答：

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<unsigned> 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];
    }
};