Python 中求目標和的骰子投擲次數

假設我們有 d 個骰子，每個骰子有 f 個面，編號為 1、2、…、f。我們需要找到投擲骰子使得向上數字之和等於目標值的可能方式的數量（在 fd 種總方式中），結果模 10^9 + 7。例如，如果輸入 d = 2，f = 6，target = 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 填充。
  • 對於 i 從 0 到 d – 1
    • 對於 j 從 0 到 t
      • 如果 i = 0，則當 j 在 1 到 f 的範圍內時，dp[i, j] := 1，否則為 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

更新於: 2020-04-30

738 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告