题目链接

Leetcode.1223 掷骰子模拟 Rating ： 2008

题目描述

有一个骰子模拟器会每次投掷的时候生成一个 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<=50001 <= n <= 50001<=n<=5000
• rollMax.length==6rollMax.length == 6rollMax.length==6
• 1<=rollMax[i]<=151 <= rollMax[i] <= 151<=rollMax[i]<=15

分析：

使用 动态规划 的方式求解。

我们定义 f(i,j,times)f(i,j,times)f(i,j,times) 为投掷了 i次骰子，并且第 i个骰子的点数是 j，且这个 j的连续出现次数是 times的不同序列数量。

按照定义，最终返回的结果为 f(n,1,1)+f(n,1,2)+...f(n,1,rollMax[0])...f(n,2,1)+f(n,2,2)...+f(n,2,rollMax[1]+...f(n,6,rollMax[5])f(n,1,1) + f(n,1,2) + ...f(n,1,rollMax[0])...f(n,2,1)+f(n,2,2)...+f(n,2,rollMax[1] + ...f(n,6,rollMax[5])f(n,1,1)+f(n,1,2)+...f(n,1,rollMax[0])...f(n,2,1)+f(n,2,2)...+f(n,2,rollMax[1]+...f(n,6,rollMax[5])。

即 ∑j=16∑times=1rollMax[j−1]f(n,j,times)\sum_{j=1}^{6}\sum_{times=1}^{rollMax[j-1]}f(n,j,times)∑j=16​∑times=1rollMax[j−1]​f(n,j,times)。

状态转移：

• 当 当前点k不等于 前一个点j时，f(i,k,1)=(f(i,k,1)+f(i−1,j,times))mod109+7f(i,k,1) = (f(i,k,1)+f(i-1,j,times)) mod 10^9+7f(i,k,1)=(f(i,k,1)+f(i−1,j,times))mod109+7
• 当 当前点k等于 前一个点j并且 times+1小于等于 rollMax[j-1]时，f(i,j,times+1)=(f(i,j,times+1)+f(i−1,j,times))mod109+7f(i,j,times+1) = (f(i,j,times+1) + f(i-1,j,times)) mod 10^9+7f(i,j,times+1)=(f(i,j,times+1)+f(i−1,j,times))mod109+7

时间复杂度：O(n∗36∗15)O(n * 36 * 15)O(n∗36∗15)

C++代码：

const int MOD = 1e9+7;
using LL = long long;
class Solution {
public:int dieSimulator(int n, vector& rollMax) {int f[n+1][7][16];memset(f,0,sizeof f);//初始化只投掷一次骰子的情况for(int i = 1;i <= 6;i++){f[1][i][1] = 1;}for(int i = 2;i <= n;i++){for(int j = 1;j <= 6;j++){for(int times = 1;times <= rollMax[j-1];times++){for(int k = 1;k <= 6;k++){if(j != k) f[i][k][1] = (f[i][k][1] + f[i-1][j][times])%MOD;else if(times + 1 <= rollMax[j - 1]){f[i][j][times+1] = (f[i][j][times+1] + f[i-1][j][times])%MOD;}}}}}LL ans = 0;//统计总的数量for(int j = 1;j <= 6;j++){for(int times = 1;times <= rollMax[j-1];times++) ans += f[n][j][times];}return ans % MOD;}
};

Java代码：

class Solution {private final int MOD = 1000_000_000+7;public int dieSimulator(int n, int[] rollMax) {int [][][] f = new int[n+1][7][16];for(int i = 1;i <= 6;i++){f[1][i][1] = 1;}for(int i = 2;i <= n;i++){for(int j = 1;j <= 6;j++){for(int times = 1;times <= rollMax[j-1];times++){for(int k = 1;k <= 6;k++){if(j != k) f[i][k][1] = (f[i][k][1] + f[i-1][j][times])%MOD;else if(times + 1 <= rollMax[j - 1]){f[i][j][times+1] = (f[i][j][times+1] + f[i-1][j][times])%MOD;}}}}}long ans = 0;for(int j = 1;j <= 6;j++){for(int times = 1;times <= rollMax[j-1];times++) ans += f[n][j][times];}return (int)(ans % MOD);}
}