[leetcode每日一题]2.10

​​1223. 掷骰子模拟​​

难度困难166

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

Solution

动态规划。

首先官方题解的做法之一是，构造一个三维数组存储状态，分别记录当前掷的是第几个骰子、当前的点数、当前点数的连续出现次数。使用这个来进行动态规划的状态转移，其转移方程为：

然后，考虑到后一个状态只与前一个状态有关，那么可以进行状态压缩：

但是其实可以不用三维数组来表示，而采用二维数组并结合数学进行状态表示。

注意到如果骰子点数x允许连续y次的话，那么我可以通过最后一次投掷的点数不为x的其他所有点数的前y次投掷(即，当前为第z次的话，z-1，z-2，……，z-y)的和来转移到当前的状态。

同时，需要注意，如果可以的话，当前状态也可以从最初没有投掷任何一个骰子的状态转移而来。这是这种做法的一个难以想到的地方。

代码(C++)

class Solution {
public:
    int dieSimulator(int n, vector<int>& rollMax) {
        long long f[5001][6] = {0};
        //初始状态设定
        for(int i=0;i<6;i++)f[1][i] = 1;
        for(int i=2;i<=n;i++){
            for(int j=0;j<6;j++){
                int cur = rollMax[j];
                //即为上面讨论的特殊情况
                if(i<=cur)f[i][j] += 1;
                for(int k=1;k<=cur&&i>k;k++){
                    f[i][j] += f[i-k][0] + f[i-k][1] + f[i-k][2] + f[i-k][3] + f[i-k][4] +f[i-k][5] - f[i-k][j];
                    f[i][j] %= 1000000007;
                }
            }
        }
        // for(int i=0;i<=n;i++){
        //     for(int j=0;j<6;j++){
        //         cout<<f[i][j]<<" ";
        //     }
        //     cout<<endl;
        // }
        return int((f[n][0] + f[n][1] + f[n][2] + f[n][3] + f[n][4] + f[n][5])%1000000007);
    }
};