[leetcode] 1155. Number of Dice Rolls With Target Sum

[leetcode] 1155. Number of Dice Rolls With Target Sum

Description

You have d dice, and each die has f faces numbered 1, 2, …, f.

Return the number of possible ways (out of fd total ways) modulo 10^9 + 7 to roll the dice so the sum of the face up numbers equals target.

Example 1:

Input: d = 1, f = 6, target = 3Output: 1Explanation: You throw one die with 6 faces. There is only one way to get a sum of 3.

Example 2:

Input: d = 2, f = 6, target = 7Output: 6Explanation: You throw two dice, each with 6 faces. There are 6 ways to get a sum of 7:1+6, 2+5, 3+4, 4+3, 5+2, 6+1.

Example 3:

Input: d = 2, f = 5, target = 10Output: 1Explanation: You throw two dice, each with 5 faces. There is only one way to get a sum of 10: 5+5.

Example 4:

Input: d = 1, f = 2, target = 3Output: 0Explanation: You throw one die with 2 faces. There is no way to get a sum of 3.

Example 5:

Input: d = 30, f = 30, target = 500Output: 222616187Explanation: The answer must be returned modulo 10^9 + 7.

Constraints:

1 <= d, f <= 301 <= target <= 1000

分析

题目的意思是：给定一个骰子，规定了掷骰子的次数和骰子的点数范围，求能够达到target的组合数。

设dp[i][j]表示掷了前i个骰子，得到总和数位为j的方案数。初始时，dp[0][0]=1,表示没有掷骰子时，得到的总方案数是1。枚举掷骰子的点数，得到递推公式

dp[i][k]=dp[i][k]+dp[i-1][k-j]

意思是用i个骰子达到k等于i-1个骰子达到k-j的和，其中j从1到f 4.最后答案为dp[d][target]

代码

class Solution: def numRollsToTarget(self, d: int, f: int, target: int) -> int: dp=[[0]*(target+1) for i in range(d+1)] dp[0][0]=1 for i in range(1,d+1): for j in range(1,f+1): for k in range(j,target+1): dp[i][k]=(dp[i][k]+dp[i-1][k-j])%(10**9+7) return dp[d][target]

参考文献

​​LeetCode 1155. Number of Dice Rolls With Target Sum​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。