पायथन में दिए गए सिक्कों के सेट से परिवर्तन करने के लिए आवश्यक सिक्कों की संख्या खोजने का प्रोग्राम

मान लीजिए हमारे पास विभिन्न मूल्यवर्ग के सिक्के हैं और पैसे की कुल राशि amount है। हमें एक फ़ंक्शन परिभाषित करना है जो उस राशि को बनाने के लिए आवश्यक सबसे कम सिक्कों की संख्या की गणना करे। जब उस राशि को सिक्कों के किसी भी संयोजन द्वारा पूरा नहीं किया जा सकता, तो -1 वापस करें। इसलिए यदि इनपुट [1,2,5] है, और राशि 64 है, तो आउटपुट 14 है। यह 12*5 + 2 + 2 = 64 का उपयोग करके बनता है।

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

यदि amount = 0, तो 0 वापस करें
यदि सिक्कों की सरणी का न्यूनतम > amount, तो -1 वापस करें
dp नामक एक सरणी परिभाषित करें, आकार amount + 1, और इसे -1 से भरें
i के लिए सिक्कों की सरणी में रेंज
- यदि i > dp की लंबाई - 1, तो अगले भाग को छोड़ें, अगले पुनरावृत्ति के लिए जाएं
- dp[i] := 1
- j के लिए i + 1 से amount तक की रेंज
  - यदि dp[j - 1] = -1, तो अगले भाग को छोड़ें, अगले पुनरावृत्ति के लिए जाएं
  - अन्यथा यदि dp[j] = -1, तो dp[j] := dp[j - i] + 1
  - अन्यथा dp[j] := dp[j] और dp[j - i] + 1 का न्यूनतम
dp[amount] वापस करें

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

उदाहरण

class Solution(object):    def coinChange(self, coins, amount):       if amount == 0 :          return 0       if min(coins) > amount:          return -1       dp = [-1 for i in range(0, amount + 1)]       for i in coins:          if i > len(dp) - 1:             continue          dp[i] = 1          for j in range(i + 1, amount + 1):             if dp[j - i] == -1:                continue             elif dp[j] == -1:                dp[j] = dp[j - i] + 1             else:                dp[j] = min(dp[j], dp[j - i] + 1)       return dp[amount] ob1 = Solution() print(ob1.coinChange([1,2,5],64))

इनपुट

[1,2,5], 64