পাইথনে দিয়ে गये কয়েনসেট দিয়ে চেঞ্জ করার ন্যূনতম কয়েন সংখ্যা খুঁজে বের করার প্রোগ্রাম

মান ল করুন বিভিন্ন ডিনোমিনেশনের কয়েন এবং amount নামের একটি টোটাল টাকা। আমাদের একটি ফাংশন ডিফাইন করতে হবে যা সেই amount বানাতে ন্যূনতম কতটি কয়েন লাগবে তা কম্পিউট করে। যদি কোনো কম্বিনেশন দিয়ে amount বানানো না যায়, -1 ফেরত দিন। ইনপুট [1,2,5] এবং amount 64 হলে আউটপুট ১৪, কারণ 12*5 + 2 + 2 = 64।

এটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলি অনুসরণ করব:

যদি amount = 0, ০ ফেরত দিন
যদি coins অ্যারের মিনিমাম > amount, -1 ফেরত দিন
dp নামের একটি অ্যারে বানান, আকার amount + 1, -1 দিয়ে ভরা
coins অ্যারে-এ থাকা প্রতিটি i-এর জন্য:
- যদি i > dp-এর দৈর্ঘ্য - ১, পরবর্তী ইটারেশনে যান
- dp[i] := 1
- j কে i+1 থেকে amount পর্যন্ত লুপ চালান:
  - যদি dp[j-i] == -1, পরবর্তী ইটারেশনে যান
  - অন্যথায় যদি dp[j] == -1, dp[j] := dp[j-i] + 1
  - অন্যথায় dp[j] := min(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