Coin Change 2 trong C++

Cho các đồng xu khác mệnh giá và tổng tiền amount. Tính số tổ hợp để tạo ra amount (mỗi mệnh giá dùng không giới hạn).

Ví dụ: amount=5, coins=[1,2,5] → 4 tổ hợp: 1+1+1+1+1, 1+1+1+2, 1+2+2, 5.

Giải thuật (DP unbounded knapsack)

• Mảng dp kích thước amount+1, dp[0]=1.
• Duyệt mỗi đồng xu coin:
  • Với j = coin .. amount: dp[j] += dp[j-coin].
• Trả về dp[amount].

Ví dụ code

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

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

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

Input

5 [1,2,5]

Output

4