পাইথনে কয়েন চেঞ্জ সমস্যা

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

এটি সমাধান করার জন্য আমরা নিচের ধাপগুলো অনুসরণ করব:

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

ইনপুট

[1,2,5] 11