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

মান ল করুন ভিন্ন ডিনোমিনেশনের কয়েন (1,5,10,25) এবং amount নামের একটি টোটাল টাকা। আমাদের একটি ফাংশন ডিফাইন করতে হবে যা amount বানাতে ন্যূনতম কতটি কয়েন লাগবে তা কম্পিউট করে। ইনপুট 64 হলে আউটপুট ৭, কারণ 25+25+10+1+1+1+1 = 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, amount):       coins = [1,5,10,25]       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(64))