题目

有一个骰子模拟器会每次投掷的时候生成一个 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

思路

dp[i][j]代表以j个连续i作为尾部的 "不同点序列" 数量

解法

class Solution {
    private static final int MOD = 1_000_000_007;

    public int dieSimulator(int n, int[] rollMax) {
        var mr = Arrays.stream(rollMax).max().getAsInt();
        var dp = new long[7][mr + 1];

        //边界条件：只有1位时每个骰子点数下的点序列数量为1
        for (int i = 1; i <= 6; i++) dp[i][1] = 1;

        //遍历次数
        for (int t = 1; t < n; t++) {
            //计算以每个以i作为尾部的序列数量和
            long all = 0; //用于快速取差
            var sums = new long[7];
            for (int i = 1; i <= 6; i++) {
                for (int j = 1; j <= rollMax[i - 1]; j++) sums[i] += dp[i][j];
                all += sums[i];
            }

            //遍历尾部数字
            for (int i = 1; i <= 6; i++) {
                //将数组横向平移一位：x长度的连续段由x-1进行转移得来
                System.arraycopy(dp[i], 1, dp[i], 2, rollMax[i - 1] - 1);
                //最低位可以由其他5位和进行转移(直接用总和作差处理)
                dp[i][1] = (all - sums[i]) % MOD;
            }
        }

        //统计下结果
        long ans = 0;
        for (int i = 1; i <= 6; i++) {
            for (int j = 1; j <= rollMax[i - 1]; j++) {
                ans += dp[i][j];
                ans %= MOD;
            }
        }
        return (int) ans;
    }
}

总结

• 分析出几种情况，然后分别对各个情况实现