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

ধরুন আমাদের কাছে d ডাইস আছে, এবং প্রতিটি ডাইতে 1, 2, ..., f নম্বরযুক্ত মুখের f সংখ্যা রয়েছে। ডাইস রোল করার জন্য আমাদের সম্ভাব্য উপায়ের সংখ্যা খুঁজে বের করতে হবে (fd ​​মোট উপায়ের মধ্যে) মডিউল 10^9 + 7 যাতে লক্ষ্যের সমান সংখ্যার সমষ্টি হয়। সুতরাং যদি ইনপুটটি d =2, f =6, লক্ষ্য =7 এর মত হয়, তাহলে আউটপুট হবে 6। তাই আমরা যদি প্রতিটি ডাইস 6টি মুখ দিয়ে নিক্ষেপ করি, তাহলে যোগফল 6 পাওয়ার 6টি উপায় আছে, যেমন 1 + 6, 2 + 5, 3 + 3, 4 + 3, 5 + 2, 6 + 1।

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

• m :=1e9 + 7
• অর্ডার d x (t + 1) এর একটি টেবিল dp তৈরি করুন এবং এটি 0 দিয়ে পূরণ করুন
• আমি 0 থেকে d – 1
  পরিসরে 0 থেকে t
  পরিসরে j-এর জন্য
  • যদি i =0, তারপর dp[i, j] :=1 যখন j রেঞ্জ 1 থেকে f, অন্যথায় 0
  • অন্যথায়
    1 থেকে f
    রেঞ্জের মধ্যে l এর জন্য
    • যদি j – l> 0 হয়, তারপর dp[i, j] :=dp[i, j] + dp[i – 1, j - l], এবং dp[i,j] :=dp[i, j] mod m
• রিটার্ন dp[d – 1, t] mod m

উদাহরণ(পাইথন)

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

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

আউটপুট

6