পাইথনে n ডাইস ফেলে নির্দিষ্ট টোটাল পাওয়ার উপায়ের সংখ্যা গণনা করার প্রোগ্রাম

মনে করুন n সংখ্যা ডাইস, ফেস সংখ্যা, এবং একটি টোটাল ভ্যালু দেওয়া আছে। n個 ডাইস ফেলে টোটাল পাওয়ার উপায়ের সংখ্যা খুঁজে বের করতে হবে। উত্তর বড় হলে 10⁹+৭ দিয়ে মড করুন।

উদাহরণস্বরূপ, n = 2, faces = 6, total = 8 হলে আউটপুট হবে 5, কারণ ২টি ৬-ফেস ডাইস দিয়ে ৮ করার ৫টি উপায়: (2,6), (6,2), (3,5), (5,3), (4,4)।

সমাধানের ধাপসমূহ

m := 10⁹ + 7
dp := (total + 1) আকারের তালিকা, 0 দিয়ে পূরিত
face = 1 থেকে min(faces, total) পর্যন্ত,
- dp[face] := 1
i = 0 থেকে n-2 পর্যন্ত,
- j = total থেকে 0 পর্যন্ত ১ কমিয়ে,
  - dp[j] := dp[j-f] এর যোগফল f=1 থেকে faces+1 পর্যন্ত যখন j-f >= 1
dp-এর শেষ উপাদান mod m ফেরত দিন

উদাহরণ

class Solution:
    def solve(self, n, faces, total):
        m = 10 ** 9 + 7
        dp = [0] * (total + 1)
        for face in range(1, min(faces, total) + 1):
            dp[face] = 1
        for i in range(n - 1):
            for j in range(total, 0, -1):
                dp[j] = sum(dp[j - f] for f in range(1, faces + 1) if j - f >= 1)
        return dp[-1] % m

ob = Solution()
n = 2
faces = 6
total = 8
print(ob.solve(n, faces, total))

ইনপুট

2,6,8