C++ এ মুদ্রা পরিবর্তন 2

ধরুন আমাদের কাছে বিভিন্ন মূল্যের কয়েন এবং মোট টাকার পরিমাণ আছে। সেই পরিমাণের সমন্বয়ের সংখ্যা গণনা করার জন্য আমাদের একটি মডিউল লিখতে হবে। আমরা অনুমান করতে পারি যে আমাদের কাছে প্রতিটি ধরণের মুদ্রার অসীম সংখ্যা রয়েছে। সুতরাং যদি পরিমাণ হয় 5 এবং কয়েন হয় [1, 2, 5], তাহলে চারটি সমন্বয় আছে। (1+1+1+1+1), (1+1+1+2), (1+2+2), (5)

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি অ্যারে ডিপি আকারের পরিমাণ + 1 তৈরি করুন
• dp[0] :=1
• n :=কয়েন অ্যারের আকার
• আমি 0 থেকে n – 1
  পরিসরে
  • j এর জন্য রেঞ্জ কয়েন[i] থেকে পরিমাণ
    • dp[j] :=dp[j – কয়েন[i]]
• রিটার্ন ডিপি[অ্যামাউন্ট]

উদাহরণ(C++)

আসুন আরও ভালোভাবে বোঝার জন্য নিচের বাস্তবায়ন দেখি −

#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;
      int n = coins.size();
      for(int i = 0; i < n; i++){
         for(int j = coins[i]; j <= amount; j++){
            dp[j] += dp[j - coins[i]];
         }
      }
      return dp[amount];
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2,5};
   cout << (ob.change(5, v));
}

ইনপুট

5
[1,2,5]

আউটপুট

4