网站正在建设中模板,网站备案需要多久时间,wordpress 自适应菜单,故事式软文广告300字1223. 掷骰子模拟
题目描述
有一个骰子模拟器会每次投掷的时候生成一个 1 到 6 的随机数。
不过我们在使用它时有个约束#xff0c;就是使得投掷骰子时#xff0c;连续 掷出数字 i 的次数不能超过 rollMax[i]#xff08;i 从 1 开始编号#xff09;。
现在#xff0c;…1223. 掷骰子模拟
题目描述
有一个骰子模拟器会每次投掷的时候生成一个 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 5000rollMax.length 61 rollMax[i] 15
算法一动态规划
思路 首先创建一个二维 dp 数组 dp[i][j] 表示第 i 次掷骰子时数字 j 出现的可能的序列总数也就是说第 i 次掷出的数字是 j 所有可能的序列数 其中 1 i n 1 j 6 。 显然 dp[1][1],dp[1][2]… dp[1][6]均为 1 所以最后结果有效序列总数就是 sum (dp[n][1] dp[n][2] … dp[n][6]) sum为求和函数 。 那么如何计算第i次骰子掷出时掷出数字为j的序列总数为多少呢 仔细思考一下dp[i][j]和什么有关? 第一: dp[i][j] 和dp[i-1][j]有关不仅如此dp[i][j] 和 dp[i-1][1], dp[i-1][2],…dp[i-1][6]都有关第二: 由于连续数字限制dp[i][j]还和 dp[i-rollMax[j-1]][1],…,dp[i-rollMax[j-1]][6]均有关所以第i次掷出骰子的序列总数只和第i-1次掷出骰子的序列总数以及第i-rollMax[j-1]次掷出骰子的序列总数有关。详细例子看题解。状态方程为 需要主要对大数的处理 使用 int 型很容易越界 另外代码中有一个特殊条件的判断当 idx 0 时ans 直接减一 此时第 1 次 ~ 第 i - 1次掷出的都是 k 即出现了序列 kkk…kk 因此不合法的情况只有一种所以减一。
算法情况
时间复杂度O6n即On空间复杂度O7n1即 On。 代码
class Solution {
public:const int MOD 1e9 7;typedef long long LL;int dieSimulator(int n, vectorint rollMax) {vectorvectorLL dp(n1, vectorLL(7));// 初始化for (int j 1; j 6; j) {dp[1][j] 1;}for (int i 2; i n; i) {for (int j 1; j 6; j) {// 加入第 i-1 次得所有可能序列总数LL ans accumulate(dp[i-1].begin(), dp[i-1].end(), 0LL);int idx i - 1 - rollMax[j-1];if (idx 1) {// 减去 i - 1 - rollMax[j-1]次掷出除j外其他五个数的所有序列总数ans accumulate(dp[idx].begin(), dp[idx].end(), ans, [](LL init, LL e) {return init MOD - e;});ans dp[idx][j];}else if (idx 0) {// 特殊情况处理ans - 1;}dp[i][j] ans % MOD;}}return accumulate(dp[n].begin(), dp[n].end(), 0LL) % MOD;}
};
参考资料
超简单动态规划 复杂度O(n)
