পাইথনে টার্গেট সম পাওয়ার ডাইস রোলের সংখ্যা

মনে করুন আমাদের d টি ডাইস আছে, এবং প্রতিটি ডাইসে f সংখ্যক ফেস রয়েছে যেগুলো ১, ২, ..., f দিয়ে নম্বর করা। আমাদের বের করতে হবে সম্ভাব্য কতভাবে (মোট f^d ভাবে) ডাইসগুলো রোল করা যাতে ফেস-আপ সংখ্যাগুলোর সম target সমান হয়, ফলাফলটি 10^9 + 7 দিয়ে মডুলো। যেমন ইনপুট d = 2, f = 6, target = 7 হলে আউটপুট হবে 6। কারণ ৬ ফেসের দুটি ডাইস থ্রো করলে সম ৭ পাওয়ার ৬ উপায় রয়েছে: ১+৬, ২+৫, ৩+৪, ৪+৩, ৫+২, ৬+১।

এটি সমাধান করতে আমরা নিচের ধাপগুলো ফলো করব:

m := 1e9 + 7
d x (t + 1) অর্ডারের একটি dp টেবিল বানান এবং ০ দিয়ে পূরণ করুন।
for i in range 0 to d - 1
- for j in range 0 to t
  - যদি i = 0, তবে dp[i, j] := 1 যখন j ১ থেকে f রেঞ্জে, অন্যথায় ০।
  - অন্যথায়:
    - for l in range 1 to f
      - যদি j - l > 0, তবে dp[i, j] := dp[i, j] + dp[i - 1, j - l], এবং dp[i,j] := dp[i, j] mod m
return dp[d - 1, t] mod m

উদাহরণ (Python)

নিচের ইমপ্লিমেন্টেশন দেখুন ভালো বুঝতে।

class Solution(object):
    def numRollsToTarget(self, d, f, t):
        mod = 1000000000 + 7
        dp = [[0 for i in range(t+1)] for j in range(d)]
        for i in range(d):
            for j in range(t+1):
                if i == 0:
                    dp[i][j] = 1 if j >= 1 and j <= f else 0
                else:
                    for l in range(1, f+1):
                        if j - l > 0:
                            dp[i][j] += dp[i-1][j-l]
                            dp[i][j] %= mod
        return dp[d-1][t] % mod

ob = Solution()
print(ob.numRollsToTarget(2, 6, 7))

ইনপুট

2 6 7