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 次浏览

开启你的 职业生涯

通过完成课程获得认证

立即开始
广告