Coin Change 2 ใน C++

โจทย์: Coin Change 2 (จำนวนวิธีทำเงิน)

ให้เหรียญมูลค่าต่างๆ coins และจำนวนเงิน amount ต้องหา จำนวนวิธี (combinations) ที่ทำให้ได้เงินเท่ากับ amount โดยใช้เหรียญแต่ละชนิด ไม่จำกัดจำนวน (unlimited) ลำดับของเหรียญไม่สำคัญ (combinations ไม่ใช่ permutations)

ตัวอย่าง: amount = 5, coins = [1, 2, 5]

วิธีที่เป็นไปได้ 4 วิธี:

1+1+1+1+1
1+1+1+2
1+2+2
5

ผลลัพธ์: 4

อัลกอริทึม: Dynamic Programming (Unbounded Knapsack / Coin Change)

กำหนด dp[i] = จำนวนวิธีทำเงินได้ i บาท

Initialization:

dp[0] = 1 (มี 1 วิธีทำเงิน 0 บาท: ไม่ใช้เหรียญเลย)

Transition:

สำหรับแต่ละเหรียญ coin ใน coins:

for (int i = coin; i <= amount; i++)
    dp[i] += dp[i - coin];

สำคัญ: วนลูปเหรียญด้านนอก, วนลูป amount ด้านใน → นับ combinations (ลำดับไม่สำคัญ) หากสลับลูป จะนับ permutations แทน

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

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

int main() {
    Solution ob;
    vector<int> v = {1, 2, 5};
    cout << ob.change(5, v) << endl;
    return 0;
}

Input

5 [1,2,5]

Output

ความซับซ้อน (Complexity)

เวลา: O(n × amount) โดย n = จำนวนชนิดเหรียญ
พื้นที่: O(amount)

ตัวอย่างเพิ่มเติม: amount = 3, coins = [2] → 0 วิธี (ทำไม่ได้) amount = 10, coins = [10] → 1 วิธี

หมายเหตุ: โจทย์นี้ต่างจาก Coin Change (LeetCode 322) ที่หา จำนวนเหรียญน้อยที่สุด** (min coins) ซึ่งใช้ dp[i] = min(dp[i], dp[i-coin]+1) และ initialize dp ด้วย INF