পাইথনে লক্ষ্যে পৌঁছানোর জন্য কয়েনের সংমিশ্রণের সংখ্যা খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের কাছে মুদ্রার একটি তালিকা এবং অন্য একটি মূল্যের পরিমাণ আছে, আমাদেরকে সেই পরিমাণের যোগফলের সংমিশ্রণের সংখ্যা খুঁজে বের করতে হবে। যদি উত্তরটি খুব বড় হয়, তাহলে ফলাফলটি 10^9 + 7 দ্বারা পরিবর্তন করুন।

সুতরাং, ইনপুট যদি কয়েনের মত হয় =[2, 5] পরিমাণ =10, তাহলে আউটপুট হবে 2, যেমন আমরা এই সমন্বয়গুলি তৈরি করতে পারি − [2, 2, 2, 2, 2], [5, 5]

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

m :=10^9 + 7
dp :=পরিমাণ + 1 এর সমান আকারের একটি তালিকা, এবং এটি 0 দিয়ে পূরণ করুন
dp[0] :=1
মুদ্রার প্রতিটি d এর জন্য, করুন
- আমি রেঞ্জ 1 থেকে dp আকারের জন্য, করুন
  - যদি i - d>=0 হয়, তাহলে
    - dp[i] :=dp[i] + dp[i - d]
রিটার্ন (dp-এর শেষ উপাদান) mod m

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

class Solution:
   def solve(self, coins, amount):
      dp = [0] * (amount + 1)
      dp[0] = 1
      for d in coins:
         for i in range(1, len(dp)):
            if i - d >= 0:
               dp[i] += dp[i - d]
      return dp[-1] % (10 ** 9 + 7)
ob = Solution()
coins = [2, 5]
amount = 10
print(ob.solve(coins, amount))

ইনপুট

[2, 5], 10