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

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

इसलिए, यदि इनपुट सिक्कों की तरह है =[2, 5] राशि =10, तो आउटपुट 2 होगा, क्योंकि हम ये संयोजन बना सकते हैं - [2, 2, 2, 2, 2], [5, 5]

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

• म :=10^9 + 7
• dp :=राशि + 1 के समान आकार की एक सूची, और इसे 0 से भरें
• dp[0] :=1
• सिक्कों में प्रत्येक d के लिए, करें
  • i श्रेणी 1 से dp के आकार के लिए, करें
    • यदि i - d>=0, तो
      • dp[i] :=dp[i] + dp[i - d]
• रिटर्न (डीपी का अंतिम तत्व) मॉड एम

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

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