โปรแกรมนับจำนวนวิธีการทอยลูกเต๋า n ลูกใน Python

สมมติว่ามีตัวเลข n จำนวนหน้า และค่ารวม เราต้องหาจำนวนวิธีที่เป็นไปได้ในการทอยลูกเต๋า n ลูกที่มีหน้าตามที่กำหนดเพื่อให้ได้ผลรวมตามต้องการ หากคำตอบใหญ่ มอดูลัสด้วย 10^9 + 7

เช่น ถ้าอินพุตคือ n = 2 faces = 6 total = 8 ผลลัพธ์จะเป็น 5 เนื่องจากมี 5 วิธีทำให้ได้ 8 ด้วยลูกเต๋า 2 ลูก 6 หน้า: (2,6), (6,2), (3,5), (5,3), (4,4)

ขั้นตอนการแก้ปัญหา

• m := 10^9 + 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

เอาต์พุต

5