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这么慢吗？