পাইথনে মুদ্রা পরিবর্তন

ধরুন আমাদের কাছে বিভিন্ন মূল্যের কয়েন এবং মোট টাকার পরিমাণ আছে। আমাদের একটি ফাংশন সংজ্ঞায়িত করতে হবে কম সংখ্যক কয়েন গণনা করার জন্য যা আমাদের সেই পরিমাণ তৈরি করতে হবে। যখন সেই পরিমাণ টাকা কয়েনের কোনো সংমিশ্রণ দ্বারা মিটমাট করা যাবে না, ফেরত দিন -1। সুতরাং যদি ইনপুট হয় [1,2,5], এবং পরিমাণ 11 হয়, আউটপুট 3 হয়। এটি 5 + 5 + 1 =11 ব্যবহার করে গঠিত হয়।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• যদি পরিমাণ =0, তাহলে 0 ফেরত দিন
• যদি ন্যূনতম কয়েন অ্যারে> পরিমাণ, তাহলে ফেরত দিন -1
• ডিপি নামক একটি অ্যারে সংজ্ঞায়িত করুন, আকারের পরিমাণ + 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