【动态规划】1223. 掷骰子模拟

2024-03-30 07:52

本文主要是介绍【动态规划】1223. 掷骰子模拟,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

作者推荐

视频算法专题

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++**实现。

这篇关于【动态规划】1223. 掷骰子模拟的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/860913

相关文章

C#如何动态创建Label,及动态label事件

《C#如何动态创建Label,及动态label事件》:本文主要介绍C#如何动态创建Label,及动态label事件,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#如何动态创建Label,及动态label事件第一点:switch中的生成我们的label事件接着,

SpringCloud动态配置注解@RefreshScope与@Component的深度解析

《SpringCloud动态配置注解@RefreshScope与@Component的深度解析》在现代微服务架构中,动态配置管理是一个关键需求,本文将为大家介绍SpringCloud中相关的注解@Re... 目录引言1. @RefreshScope 的作用与原理1.1 什么是 @RefreshScope1.

MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

《MyBatis动态SQL优化之标签的实战与技巧(常见用法)》本文通过详细的示例和实际应用场景,介绍了如何有效利用这些标签来优化MyBatis配置,提升开发效率,确保SQL的高效执行和安全性,感... 目录动态SQL详解一、动态SQL的核心概念1.1 什么是动态SQL?1.2 动态SQL的优点1.3 动态S

mybatis-plus 实现查询表名动态修改的示例代码

《mybatis-plus实现查询表名动态修改的示例代码》通过MyBatis-Plus实现表名的动态替换,根据配置或入参选择不同的表,本文主要介绍了mybatis-plus实现查询表名动态修改的示... 目录实现数据库初始化依赖包配置读取类设置 myBATis-plus 插件测试通过 mybatis-plu

基于Canvas的Html5多时区动态时钟实战代码

《基于Canvas的Html5多时区动态时钟实战代码》:本文主要介绍了如何使用Canvas在HTML5上实现一个多时区动态时钟的web展示,通过Canvas的API,可以绘制出6个不同城市的时钟,并且这些时钟可以动态转动,每个时钟上都会标注出对应的24小时制时间,详细内容请阅读本文,希望能对你有所帮助...

CSS模拟 html 的 title 属性(鼠标悬浮显示提示文字效果)

《CSS模拟html的title属性(鼠标悬浮显示提示文字效果)》:本文主要介绍了如何使用CSS模拟HTML的title属性,通过鼠标悬浮显示提示文字效果,通过设置`.tipBox`和`.tipBox.tipContent`的样式,实现了提示内容的隐藏和显示,详细内容请阅读本文,希望能对你有所帮助... 效

Vue中动态权限到按钮的完整实现方案详解

《Vue中动态权限到按钮的完整实现方案详解》这篇文章主要为大家详细介绍了Vue如何在现有方案的基础上加入对路由的增、删、改、查权限控制,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、数据库设计扩展1.1 修改路由表(routes)1.2 修改角色与路由权限表(role_routes)二、后端接口设计

前端 CSS 动态设置样式::class、:style 等技巧(推荐)

《前端CSS动态设置样式::class、:style等技巧(推荐)》:本文主要介绍了Vue.js中动态绑定类名和内联样式的两种方法:对象语法和数组语法,通过对象语法,可以根据条件动态切换类名或样式;通过数组语法,可以同时绑定多个类名或样式,此外,还可以结合计算属性来生成复杂的类名或样式对象,详细内容请阅读本文,希望能对你有所帮助...

Nginx实现动态封禁IP的步骤指南

《Nginx实现动态封禁IP的步骤指南》在日常的生产环境中,网站可能会遭遇恶意请求、DDoS攻击或其他有害的访问行为,为了应对这些情况,动态封禁IP是一项十分重要的安全策略,本篇博客将介绍如何通过NG... 目录1、简述2、实现方式3、使用 fail2ban 动态封禁3.1 安装 fail2ban3.2 配

Vue3中的动态组件详解

《Vue3中的动态组件详解》本文介绍了Vue3中的动态组件,通过`component:is=动态组件名或组件对象/component`来实现根据条件动态渲染不同的组件,此外,还提到了使用`markRa... 目录vue3动态组件动态组件的基本使用第一种写法第二种写法性能优化解决方法总结Vue3动态组件动态