题目大意：
掷骰子模拟
有一个骰子模拟器会每次投掷的时候生成一个 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 <= 5000rollMax.length == 61 <= rollMax[i] <= 15
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1223
解题思路分析：
这道题可以使用DP也可以使用递归加memo数组来做。其实这两种手法的时间复杂度是一样的。
理论上如果没有连续投掷的次数限制，结果应该为6的N次方。加上次数限制之后问题就变得稍微复杂一些，我们要判断当前投掷时哪些数字不能出现。我们可以利用一个dfs递归方法，遍历每一种可能。方法的参数需要传入前一次投掷的数字，以及前数字连续出现的次数。方法内部，我们循环6个数字，如果与前数字不同则一定能被掷出，如果相同，则看前数字连续出现的次数是否达到要求的上限，没达到是也可被掷出，反之则不能。如果当前数字能被投掷，则继续向下dfs。累加6个数字的dfs结果构成当前的返回结果。
看下实现代码：
Integer[][][] memo; // 记忆数组，避免重复计算
public int dieSimulator(int n, int[] rollMax) {
// 初始化记忆数组
memo = new Integer[7][16][n+1];
return help(n, rollMax, 0, 0); // 开始dfs所有线路
}
// preNum为前一次投掷的数字
// length代表前数字连续出现的次数
private int help(int n, int[] rollMax, int preNum, int length){
if(n==0){
return 1;
}
// 记忆数组不为空，直接返回该值
if(memo[preNum][length][n] != null){
return memo[preNum][length][n];
}
int sum=0; // 返回值
for(int i=1; i<=6;i++){
// 当前数字等于前数字，并且连续次数没达到上限
if(i==preNum && length<rollMax[i-1]){
// 当前数字可以继续dfs，投掷次数减一，连续长度加一
sum=(sum+help(n-1, rollMax, i, length+1))%1000000007;
}else if(i!=preNum){
// 当前数字与前数字不同
// 当前数字可以继续dfs，投掷次数减一，连续为1
sum=(sum+help(n-1, rollMax, i, 1))%1000000007;
}
}
memo[preNum][length][n] = sum; // 将结果保存至记忆数组
return sum;
} 本题解法执行时间为29ms。
Runtime: 29 ms, faster than 53.62% of Java online submissions for Dice Roll Simulation.
Memory Usage: 42.2 MB, less than 100.00% of Java online submissions for Dice Roll Simulation.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1223-dice-roll-simulation解题思路分析/