Python程式：計算擲n個骰子的方法數

假設我們有一個數字n，表示骰子的面數，以及一個總值，我們需要找到擲n個骰子（每個骰子有faces個面）得到該總值的可能方法數。如果答案非常大，則將結果模 10**9 + 7。

例如，如果輸入為 n = 2，faces = 6，total = 8，則輸出將為 5，因為用2個6面骰子得到8有5種方法：（2 和 6），（6 和 2），（3 和 5），（5 和 3），（4 和 4）。

為了解決這個問題，我們將遵循以下步驟：

  • m := 10^9 + 7

  • dp := 一個大小為 (total + 1) 的列表，並用0填充

  • 對於範圍為1到faces的最小值的face，在每個步驟中更新 total + 1，執行：

    • dp[face] := 1

  • 對於範圍為0到n - 2的i，執行：

    • 對於範圍為total到0的j，遞減1，執行：

    • dp[j] := 所有dp[j - f]的和，其中f的範圍為1到faces + 1，且j - f >= 1

  • 返回dp的最後一個元素模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

更新時間： 2020年10月7日

197 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

立即開始
廣告