LeetCode1223.掷骰子模拟（DP）Michael是个半路程序员-

1. 题目

有一个骰子模拟器会每次投掷的时候生成一个 1 到 6 的随机数。

不过我们在使用它时有个约束，就是使得投掷骰子时，连续 掷出数字 i 的次数不能超过 rollMax[i]（i 从 1 开始编号）。

现在，给你一个整数数组 rollMax 和一个整数 n，请你来计算掷 n 次骰子可得到的不同点数序列的数量。

假如两个序列中至少存在一个元素不同，就认为这两个序列是不同的。
由于答案可能很大，所以请返回 模 10^9 + 7 之后的结果。

示例 1： 输入：n = 2, rollMax = [1,1,2,2,2,3] 输出：34 解释：我们掷 2 次骰子，如果没有约束的话，共有 6 * 6 = 36 种可能的组合。 但是根据 rollMax 数组，数字 1 和 2 最多连续出现一次， 所以不会出现序列 (1,1) 和 (2,2)。因此，最终答案是 36-2 = 34。  示例 2： 输入：n = 2, rollMax = [1,1,1,1,1,1] 输出：30  示例 3： 输入：n = 3, rollMax = [1,1,1,2,2,3] 输出：181   提示： 1 <= n <= 5000 rollMax.length == 6 1 <= rollMax[i] <= 15 

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/dice-roll-simulation
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

类似题目：
LeetCode 1155. 掷骰子的N种方法（DP）
剑指Offer – 面试题60. n个骰子的点数（动态规划）

• 样本维度 i
• 状态维度投出的是几点（上一次，当前次）j，nj
• 投出的点，连续了几次 k

class Solution { //C++ public: int dieSimulator(int n, vector<int>& rollMax) {      vector<vector<vector<int>>> dp(n,vector<vector<int>>(6,vector<int>(16,0))); int i,j,nj,k; for(j = 0; j < 6; ++j) { //初始化       dp[0][j][1] = 1;//0次投出j点，j连续了1次的方案数 } for(i = 1; i < n; ++i) { //后序的样本 for(j = 0; j < 6; ++j) { //前一次投出的点数 for(k = 1; k <= 15; ++k) { //前一次的最后的点数连续了几次 if(dp[i-1][j][k] != 0) { //状态存在 for(nj = 0; nj < 6; ++nj) { //这一次投的点数 if(nj == j && k+1 <= rollMax[j])//跟上一次一样的点且连续次数不超            dp[i][nj][k+1] = (dp[i][nj][k+1]+dp[i-1][j][k])%1000000007; if(nj != j)//跟上一次不一样，连续次数变为1次            dp[i][nj][1] = (dp[i][nj][1]+dp[i-1][j][k])%1000000007; } } } } } int sum = 0; for(j = 0; j < 6; ++j) { //求和 for(k = 1; k <= 15; ++k)        sum = (sum+dp[n-1][j][k])%1000000007; } return sum; } }; 

288 ms 30.7 MB

class Solution: def dieSimulator(self, n: int, rollMax: List[int]) -> int:         dp = [[[0 for i in range(16)] for i in range(6)] for i in range(n)] for j in range(6):             dp[0][j][1] = 1 for i in range(1,n): for j in range(6): for k in range(1,16): if dp[i-1][j][k]==0: continue for nj in range(6): if nj==j and k+1 <= rollMax[j]:                             dp[i][nj][k+1] = (dp[i][nj][k+1]+dp[i-1][j][k])%1000000007 if nj!=j:                             dp[i][nj][1] = (dp[i][nj][1]+dp[i-1][j][k])%1000000007; sum = 0 for j in range(6): for k in range(1,16): sum = (sum+dp[n-1][j][k])%1000000007 return sum 

2776 ms 30 MB

python这么慢吗？😂