leetcode 5224 掷骰子模拟

缘起

日常水题~ leetcode 5224 掷骰子模拟

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
有一个骰子模拟器会每次投掷的时候生成一个 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. 令dp[i][j][k] 是前i个骰子, 最后一位是j, 并且它的连续次数是k的方法数. 则我们注意到

1
dp[i][j][k]=dp[i-1][j][k-1], for k>1, 即dp[i][j][k]=dp[i-k+1][j][1]，记这个规律为（甲）

则就知道了本题不需要进行三维计数dp. 而只需要令

1
2
dp[i][j]为前i个骰子, 最后一个是j, 而且它是孤零零的一个的方法数. 
即例如 11332223 这种, i=8, j=3, 3是孤零零的

则根据第i-1位是哪一个骰子jj（jj!=j, 因为j是孤零零的）分类，可以得到下面的dp公式

注意, 上面的式子用到了上面提及的规律（甲）——即将第i-1的骰子为jj, 并且连续了k位转换为了第 i-k+1位为孤零零的jj的情况.

然后只需做差dp[i][j]-dp[i-1][j], 即可得到最终的dp公式

ps: 写错了,是 rollmax[jj]+2而不是rollmax[j]+2

所以我们需要初始化dp[1]和dp[2]. 而且注意到上面的式子——仅仅在i>rollmax[j]+1的时候，第二个sigma求和才有意义. 最后的答案就是

1
2
3
4
5
6
7
8
9
10
11
dp[n][1][1]+...+dp[n][1][rollmax[1]]
+
dp[n][2][1]+...+dp[n][2][rollmax[2]]
+
dp[n][3][1]+...+dp[n][3][rollmax[3]]
+
dp[n][4][1]+...+dp[n][4][rollmax[4]]
+
dp[n][5][1]+...+dp[n][5][rollmax[5]]
+
dp[n][6][1]+...+dp[n][6][rollmax[6]]

而根据上面提到的规律（甲），是可以将上面的式子转换为 

1
dp[i][1][1]、dp[i][2][1]、dp[i][3][1]、dp[i][4][1]、dp[i][5][1]、dp[i][6][1]

的.

则不难写下如下ac代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
class Solution {
public:
	int dieSimulator(int n, vector<int>& rointMax) 
	{
		memset(dp,-1,sizeof(dp));
		for (int j = 1;j<=6;j++)
		{
			dp[1][j] = 1;
			dp[2][j] = 5;
		} // dp初始化
		int ans = 0;
		for (int j = 1; j<=6; j++)
		{
			ans+=mm(n, j, rointMax);
			ans%=MOD;
		}
		return ans%MOD;
	}

	const static int MOD = 1e9+7;

	int dp[5005][7]; // dp[i][j]意为前i个数位, 最后那次(即第i次)为j, 并且它是孤零零的一个1的方法数, 即例如 11332223 这种, i=8, j=3, 3是孤零零的

	int kk(int i, int j, vector<int> &rointMax) // 我dp个锤子~ 空间复杂度允许的情况下都记忆化搜索
	{
		if (~dp[i][j])
		{
			return dp[i][j];
		}
		int ans = 0;
		for (int jj = 1; jj<=6; jj++)
		{
			ans+=kk(i-1, jj, rointMax);
			ans%=MOD;
			if (jj!=j && i>rointMax[jj-1]+1)
			{
				int t = kk(i-rointMax[jj-1]-1,jj, rointMax)%MOD;
				ans-=t;
				ans%=MOD;
				if (ans<0) // 注意对负数余数的处理
				{
					ans = (ans+MOD)%MOD; 
				}
			}
		}
		return dp[i][j] = ans%MOD;
	} // kk保证返回的结果为非负

	int mm(int i, int j,  vector<int> &rointMax)
	{
		int ans = 0;
		for (int a = 0;a<rointMax[j-1] && a<i; a++)
		{
			ans+=kk(i-a, j, rointMax);
			ans%=MOD;
		}
		return ans%MOD;
	}
};

ac情况

1
2
3
4
5
6
7
8
9
10
11
12
13
执行结果：
通过
显示详情
执行用时 :
24 ms
, 在所有 cpp 提交中击败了
100.00%
的用户
内存消耗 :
8.8 MB
, 在所有 cpp 提交中击败了
100.00%
的用户