掷骰子模拟【LC1223】
有一个骰子模拟器会每次投掷的时候生成一个 1 到 6 的随机数。
不过我们在使用它时有个约束，就是使得投掷骰子时，连续 掷出数字 i 的次数不能超过 rollMax[i]（i 从 1 开始编号）。
现在，给你一个整数数组 rollMax 和一个整数 n，请你来计算掷 n 次骰子可得到的不同点数序列的数量。
假如两个序列中至少存在一个元素不同，就认为这两个序列是不同的。由于答案可能很大，所以请返回 模 10^9 + 7 之后的结果。
啊啊啊激动 自己写出来了！！！
记忆化搜索+dp
- 思路：
- 由于方案数与当前为第几次掷骰子、前一个骰子值及其连续次数相关，并且整个回溯过程是有大量重复递归调用的，因此可以采用记忆化搜索和dp的方法实现
实现
- 初始时，将
dp数组置为-1 - f函数的搜索过程为：
- 如果已经掷完所有骰子，即
i==1时，那么返回1 - 如果当前状态已经搜索过，那么返回dp数组中的值
- 如果以上情况都不符合，那么枚举本次骰子可能的值，并将可能的方案数记录在dp数组中
- 如果骰子值与前一次相同，那么需要判断连续的次数是否小于
rollMax - 如果骰子值与前一次不相同，那么更改骰子值，并将次数置为1，继续搜索
class Solution { public static final int MOD = (int)(1e9 + 7); int[][][] dp; int[] rollMax; int n; public int dieSimulator(int n, int[] rollMax) { this.n = n; this.rollMax = rollMax; int max = 0; for (int roll : rollMax){ max = Math.max(roll, max); } dp = new int[n][6][max + 1]; for (int i = 0; i < dp.length; i++){ for (int j = 0; j < dp[0].length; j++){ Arrays.fill(dp[i][j], -1);// 没有访问过 } } return f(0, -1, 1); } public int f(int i, int pre, int count){ if (i == n) return 1; if (pre >= 0 && count >= 0 && dp[i][pre][count] != -1) return dp[i][pre][count]; int res = 0; for (int num = 0; num < 6; num++){ if (num == pre && count >= rollMax[num]) continue; res = (res + f(i + 1, num, num == pre ? count + 1 : 1) ) % MOD; } if (pre >= 0 && count >= 0) dp[i][pre][count] = res; return res; } }
dp数组的形式
定义状态 d[i][j][k]表示已经完成了 i次掷骰子，第 i次掷的是 j，并且已经连续掷了 k次 j的合法序列数。
class Solution { private static final long MOD = (long) 1e9 + 7; public int dieSimulator(int n, int[] rollMax) { int m = rollMax.length; // 6 var f = new int[n][m][15]; for (int j = 0; j < m; ++j) Arrays.fill(f[0][j], 1); for (int i = 1; i < n; ++i) for (int last = 0; last < m; ++last) for (int left = 0; left < rollMax[last]; ++left) { long res = 0; for (int j = 0; j < m; ++j) if (j != last) res += f[i - 1][j][rollMax[j] - 1]; else if (left > 0) res += f[i - 1][j][left - 1]; f[i][last][left] = (int) (res % MOD); } long ans = 0; for (int j = 0; j < m; ++j) ans += f[n - 1][j][rollMax[j] - 1]; return (int) (ans % MOD); } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/dice-roll-simulation/solutions/2103292/jiao-ni-yi-bu-bu-si-kao-dong-tai-gui-hua-sje6/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
