C++ में Coin Change 2

मान लीजिए हमारे पास विभिन्न मूल्यवर्ग के सिक्के और धन की कुल राशि है। हमें एक मॉड्यूल लिखना है जो उस राशि को बनाने वाले संयोजनों की संख्या की गणना करे। हम मान सकते हैं कि हमारे पास प्रत्येक प्रकार के सिक्के की अनंत संख्या है। इसलिए यदि राशि 5 है और सिक्के [1, 2, 5] हैं, तो चार संयोजन हैं। (1+1+1+1+1), (1+1+1+2), (1+2+2), (5)

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• amount + 1 आकार की एक सरणी dp बनाएं
• dp[0] := 1
• n := coins सरणी का आकार
• i को 0 से n - 1 तक की रेंज में
  • j को coins[i] से amount तक की रेंज में
    • dp[j] := dp[j - coins[i]]
• dp[amount] लौटाएं

उदाहरण (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