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 की सीमा में
  • जे श्रेणी के सिक्कों के लिए[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