Số cuộn xúc xắc có tổng mục tiêu bằng Python

Giả sử chúng ta có d con xúc xắc và mỗi con súc sắc có f số mặt được đánh số 1, 2, ..., f. Ta phải tìm số cách có thể (trong tổng số cách) modulo 10 ^ 9 + 7 để tung xúc xắc sao cho tổng các số có mặt ngửa bằng đích. Vì vậy, nếu đầu vào là d =2, f =6, target =7, thì đầu ra sẽ là 6. Vì vậy, nếu chúng ta ném mỗi con xúc xắc có 6 mặt, thì có 6 cách để lấy tổng 6, như 1 + 6, 2 + 5, 3 + 3, 4 + 3, 5 + 2, 6 + 1.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• m:=1e9 + 7
• lập một bảng dp theo thứ tự d x (t + 1) và điền vào bảng này bằng 0
• cho tôi trong phạm vi từ 0 đến d - 1
  • cho j trong phạm vi từ 0 đến t
    • nếu i =0, thì dp [i, j]:=1 khi j trong phạm vi từ 1 đến f, nếu không thì 0
    • nếu không thì
      • cho l trong phạm vi 1 đến f
        • nếu j - l> 0, thì dp [i, j]:=dp [i, j] + dp [i - 1, j - l] và dp [i, j]:=dp [i, j] mod m
• return dp [d - 1, t] mod m

Ví dụ (Python)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

2
6
7

Đầu ra

6