Chương trình đếm số cách chúng ta có thể ném n con xúc xắc trong Python

Giả sử chúng ta có một số n, số mặt và tổng giá trị, chúng ta phải tìm số cách có thể ném n con xúc xắc với mỗi mặt để được tổng. Nếu câu trả lời là rất lớn, hãy mod kết quả là 10 ** 9 + 7.

Vì vậy, nếu đầu vào là n =2 mặt =6 tổng =8, thì đầu ra sẽ là 5, vì có 5 cách tạo 8 với 2 viên xúc xắc 6 mặt:(2 và 6), (6 và 2) , (3 và 5), (5 và 3), (4 và 4).

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

m:=10 ^ 9 + 7
dp:=danh sách kích thước (tổng + 1) rồi điền 0
đối với khuôn mặt trong phạm vi từ 1 đến tối thiểu khuôn mặt, hãy cập nhật từng bước theo tổng số + 1, thực hiện
- dp [khuôn mặt]:=1
đối với tôi trong phạm vi từ 0 đến n - 2, hãy thực hiện
- cho j trong phạm vi tổng cộng là 0, giảm 1, thực hiện
- dp [j]:=tổng của tất cả dp [j - f] đối với f trong phạm vi 1 đến các mặt + 1 khi j - f> =1
trả về phần tử cuối cùng của dp mod m

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

Ví dụ

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

Đầu vào

2,6,8

Chương trình đếm số cách chúng ta có thể ném n con xúc xắc trong Python

Ví dụ

Đầu vào

Đầu ra