पायथन में टार्गेट तक पहुंचने के लिए सिक्कों के संयोजनों की संख्या खोजने का प्रोग्राम

मान लीजिए हमारे पास सिक्कों की एक सूची और एक मान amount है, हमें उन संयोजनों की संख्या ढूंढनी है जिनका योग amount है। यदि उत्तर बहुत बड़ा है, तो परिणाम को 10^9 + 7 से मॉड करें।

उदाहरण के लिए, यदि इनपुट coins = [2, 5] और amount = 10 है, तो आउटपुट 2 होगा, क्योंकि हम ये संयोजन बना सकते हैं: [2,2,2,2,2], [5,5]।

समाधान दृष्टिकोण

इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे (कॉइन चेंज 2 - डायनामिक प्रोग्रामिंग):

• m := 10^9 + 7
• dp := आकार amount+1 की सूची, 0 से भरी
• dp[0] := 1
• प्रत्येक सिक्का d के लिए coins में:
  • i को 1 से len(dp) तक:
    • यदि i-d >= 0:
      • dp[i] := dp[i] + dp[i-d]
• dp[-1] % m लौटाएं

उदाहरण कोड

class Solution:
    def solve(self, coins, amount):
        dp = [0] * (amount + 1)
        dp[0] = 1
        for d in coins:
            for i in range(1, len(dp)):
                if i - d >= 0:
                    dp[i] += dp[i - d]
        return dp[-1] % (10**9 + 7)

ob = Solution()
coins = [2, 5]
amount = 10
print(ob.solve(coins, amount))

इनपुट

[2, 5], 10

आउटपुट

2