পাইথনে প্রদত্ত কয়েনের সেটের সাথে পরিবর্তন করার জন্য প্রয়োজনীয় কয়েনের সংখ্যা খুঁজে বের করার প্রোগ্রাম

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

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

যদি পরিমাণ =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)
      return dp[amount]
ob1 = Solution()
print(ob1.coinChange([1,2,5],64))

ইনপুট

[1,2,5], 64