পাইথনে কয়েন কম্বিনেশন দিয়ে টার্গেট অ্যামাউন্ট পাওয়ার উপায়ের সংখ্যা বের করার প্রোগ্রাম

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

উদাহরণস্বরূপ, যদি ইনপুট হয় coins = [2, 5] এবং amount = 10, তবে আউটপুট হবে 2, কারণ আমরা এই কম্বিনেশনগুলো বানাতে পারি: [2, 2, 2, 2, 2], [5, 5]।

• m := 10^9 + 7
• dp := আকার amount+1 এমন একটি তালিকা ০ দিয়ে ভরা।
• dp[0] := 1
• প্রতিটি d এর জন্য coins-এ:
  • i কে ১ থেকে len(dp) পর্যন্ত লুপ চালান:
    • যদি i - d >= 0 হয়, তবে dp[i] := dp[i] + dp[i-d]
• dp[-1] % 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

2