C++-এ Coin Change 2

এই সমস্যায় বিভিন্ন ডেনোমিনেশনের কয়েন এবং একটি টোটাল অ্যামাউন্ট দেওয়া থাকলে, সেই অ্যামাউন্ট তৈরির কতটি কবিনেশন সম্ভব তা বের করতে হবে। প্রতিটি কয়েন অনলিমিটেড সংখ্যক ব্যবহার করা যায়।

উদাহরণ: amount = 5, coins = [1,2,5] -> আউটপুট 4। কবিনেশন: (1,1,1,1,1), (1,1,1,2), (1,2,2), (5)।

সমাধানের পদ্ধতি (Dynamic Programming - Unbounded Knapsack)

dp[i] = অ্যামাউন্ট i তৈরির কবিনেশনের সংখ্যা।
dp[0] = 1 (০ তৈরির ১ উপায়: কোনো কয়েন নেই)।
প্রতিটি কয়েন c এর জন্য, c থেকে amount পর্যন্ত:
- dp[j] += dp[j - c]।
বাহের লুপ কয়েনের ওপর, ভিতরের লুপ অ্যামাউন্টের ওপর -> অর্ডার মানে না (কবিনেশন)।

উদাহরণ (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 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;
}

ইনপুট

5 [1,2,5]