Python 中掷骰子次数和目标和
pythonserver side programmingprogramming
假设我们有 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
- 对于 l，范围为 1 到 f
- 对于 j，范围为 0 到 t
示例 (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
