पायथन में सिक्का बदलें

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

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

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

उदाहरण

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

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)
         #print(dp)
      return dp[amount]
ob1 = Solution()
print(ob1.coinChange([1,2,5], 11))

इनपुट

[1,2,5]
11

आउटपुट

3