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

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告