做果蔬零售的网站,湖北系统app定制开发系统,荥阳网站制作,花都网站(建设信科网络)1. 题目
这里有 d 个一样的骰子#xff0c;每个骰子上都有 f 个面#xff0c;分别标号为 1, 2, …, f。
我们约定#xff1a;掷骰子的得到总点数为各骰子面朝上的数字的总和。
如果需要掷出的总点数为 target#xff0c;请你计算出有多少种不同的组合情况#xff08;所…1. 题目
这里有 d 个一样的骰子每个骰子上都有 f 个面分别标号为 1, 2, …, f。
我们约定掷骰子的得到总点数为各骰子面朝上的数字的总和。
如果需要掷出的总点数为 target请你计算出有多少种不同的组合情况所有的组合情况总共有 fdf^dfd 种模 10^9 7 后返回。
示例 1
输入d 1, f 6, target 3
输出1示例 2
输入d 2, f 6, target 7
输出6示例 3
输入d 2, f 5, target 10
输出1示例 4
输入d 1, f 2, target 3
输出0示例 5
输入d 30, f 30, target 500
输出222616187提示
1 d, f 30
1 target 1000来源力扣LeetCode 链接https://leetcode-cn.com/problems/number-of-dice-rolls-with-target-sum 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
类似题目 剑指Offer - 面试题60. n个骰子的点数动态规划 LeetCode 1223. 掷骰子模拟DP
从上一次的所有状态推导当前次的状态
class Solution { // C
public:int numRollsToTarget(int d, int f, int target) {vectorvectorint dp(d1,vectorint(target1, 0));dp[0][0] 1;int i,j,k;for(i 1; i d; i){for(j 0; j target; j){if(dp[i-1][j] ! 0)//上一次的状态存在{for(k 1; k f; k){if(jk target)//状态转移dp[i][jk] (dp[i][jk]dp[i-1][j])%1000000007;}}}}return dp[d][target];}
};36 ms 8.7 MB
python3 注意二维数组的写法
class Solution:# py3def numRollsToTarget(self, d: int, f: int, target: int) - int:dp [[0 for i in range(target1)] for i in range(d1)]dp[0][0] 1for i in range(1,d1):for j in range(0, target):if dp[i-1][j]0:continuefor k in range(1, f1):if jk target:dp[i][jk] (dp[i][jk]dp[i-1][j])%1000000007return dp[d][target]524 ms 13.9 MB
