作者推荐
视频算法专题
LeetCode1223. 掷骰子模拟
有一个骰子模拟器会每次投掷的时候生成一个 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][k] 表示投掷(i+1)次骰子后,以j结尾,且j重复k次的子序列数量。状态数量:n × \times × 6 × \times × 15
动态规划的转移方程
对每种状态,分别枚举投掷0到5。
动态规划的初始状态
分别投掷了0到5。
动态规划的填表顺序
i从0到n-1。
动态规范的返回值
sub(dp.back())
优化
优化一
第i次选择和i-1次选择相同,k++。
第i次选择和i-1次选择不同。k =1。 dp[i-1]的合法状态和*5。5种不同值。
时间复杂度优化到:O(n
×
\times
× 6
×
\times
× 15)。
优化二
状态不需要k。
dp[i][j]的含义不变。dp2[i][j] 一个j结尾的合法序列。
iSum = sum(dp[i-1])
dp[i][j] = iSum - dp[i-1][j]中连续maxRoll[j]个j结尾的子序列,即dp2[i-maxRoll[j]]。
dp2[i][j] = iSum - dp[i-1][j]。
优化后,时间复杂度O(n*6)。
代码
核心代码
class Solution {
public:
int dieSimulator(int n, vector<int>& rollMax) {
vector<vector<C1097Int<>>> dp(n,vector<C1097Int<>>(6));
dp[0].assign(6,1);
auto dp2 = dp;
for (int i = 1; i < n; i++)
{
auto sumPre = std::accumulate(dp[i - 1].begin(), dp[i - 1].end(), C1097Int<>());
for (int iRoll = 0; iRoll < 6; iRoll++)
{
dp2[i][iRoll] = sumPre - dp[i - 1][iRoll];
dp[i][iRoll] = sumPre ;
const int delIndex = i - (rollMax[iRoll]);
if (delIndex >= 0)
{
dp[i][iRoll] -= dp2[delIndex][iRoll];
}
}
}
return std::accumulate(dp.back().begin(), dp.back().end(), C1097Int<>()).ToInt();
}
};
测试用例
template<class T, class T2>
void Assert(const T& t1, const T2& t2)
{
assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
Assert(v1[i], v2[i]);
}
}
int main()
{
int n;
vector<int> rollMax;
{
n = 2, rollMax = { 1,1,2,2,2,3 };
int res = Solution().dieSimulator(n, rollMax);
Assert(34, res);
}
{
n = 3, rollMax = { 1,1,1,2,2,3 };
int res = Solution().dieSimulator(n, rollMax);
Assert(181, res);
}
{
n = 2, rollMax = { 1,1,1,1,1,1 };
int res = Solution().dieSimulator(n, rollMax);
Assert(30, res);
}
{
n = 4, rollMax = { 2, 1, 1, 3, 3, 2 };
int res = Solution().dieSimulator(n, rollMax);
Assert(1082, res);
}
}
扩展阅读
视频课程
有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关
下载
想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
我想对大家说的话 |
---|
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。 |
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。 |
如果程序是一条龙,那算法就是他的是睛 |
测试环境
操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。文章来源:https://www.toymoban.com/news/detail-852482.html
文章来源地址https://www.toymoban.com/news/detail-852482.html
到了这里,关于【动态规划】1223. 掷骰子模拟的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!