จำนวนลูกเต๋าทอยด้วยผลรวมเป้าหมายใน Python

สมมุติว่าเรามี d dice และแต่ละลูกเต๋ามีเลขหน้า f เลข 1, 2, ..., f. เราต้องหาจำนวนวิธีที่เป็นไปได้ (จากวิธีทั้งหมด) โมดูโล 10^9 + 7 เพื่อทอยลูกเต๋า ดังนั้นผลรวมของตัวเลขที่หงายหน้าขึ้นเท่ากับเป้าหมาย ดังนั้นหากอินพุตเป็น d =2, f =6, เป้าหมาย =7, ผลลัพธ์จะเป็น 6 ดังนั้นหากเราโยนลูกเต๋าแต่ละลูกที่มี 6 หน้า แล้วมี 6 วิธีที่จะได้ผลรวม 6 เช่น 1 + 6 2 + 5, 3 + 3, 4 + 3, 5 + 2, 6 + 1.

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ม :=1e9 + 7
• สร้างตาราง dp ของคำสั่ง d x (t + 1) และเติมด้วย 0
• สำหรับ i ในช่วง 0 ถึง d – 1
  • สำหรับ j ในช่วง 0 ถึง t
    • ถ้า i =0 แล้ว dp[i, j] :=1 เมื่อ j อยู่ในช่วง 1 ถึง f มิฉะนั้น 0
    • อย่างอื่น
      • สำหรับ l ในช่วง 1 ถึง f
        • ถ้า 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

ตัวอย่าง(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

ผลลัพธ์

6