【动态规划】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++**实现。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/291040.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

CXL事务层(续)

3.2 CXL.cache 3.2.1 概览 CXL.cache协议将设备和主机之间的交互定义为多个请求&#xff0c;每个请求至少有一条相关的响应消息&#xff0c;有时还有数据传输。该接口在每个方向上由三个通道组成&#xff1a;请求&#xff08;Request&#xff09;、响应&#xff08;Response&…

ESCTF-密码赛题WP

*小学生的爱情* Base64解码获得flag *中学生的爱情* 社会主义核心价值观在线解码得到flag http://www.atoolbox.net/Tool.php?Id850 *高中生的爱情* U2FsdG开头为rabbit密码,又提示你密钥为love。本地toolfx密码工具箱解密。不知道为什么在线解密不行。 *大学生的爱情* …

Django屏蔽Server响应头信息

一、背景 最近我们被安全部门的漏洞扫描工具扫出了一个服务端口的漏洞。这个服务本身是一个Django启动的web服务&#xff0c;并且除了登录页面&#xff0c;其它页面或者接口都需要进行登录授权才能进行访问。 漏洞扫描信息和提示修复信息如下: 自然这些漏洞如何修复&#xff0c…

mysql之MyBatis核心工作原理

MyBatis核心工作原理 一、源码环境 1.手动编译源码 工欲善其事必先利其器。为了方便我们在看源码的过程中能够方便的添加注释&#xff0c;我们可以自己来从官网下载源码编译生成对应的Jar包&#xff0c;然后上传到本地maven仓库&#xff0c;再引用这个Jar。大家可以自行去官…

如何用Python脚本自动发送邮件?

目录 1. 基础知识 1.1. SSH&#xff08;Secure Shell&#xff09;协议 1.2. SMTP&#xff08;Simple Mail Transfer Protocol&#xff09;协议 1.3. SSH协议与SMTP协议之间的关系 2. QQ邮箱设置 2.1. 开启SMTP服务 2.2. 编写脚本 3. 测试成功 1. 基础知识 邮件的发送过…

学习鸿蒙基础(7)

一、Watch状态变量更改通知 Watch应用于对状态变量的监听。如果开发者需要关注某个状态变量的值是否改变&#xff0c;可以使用Watch为状态变量设置回调函数。 1、装饰器参数&#xff1a;必填。常量字符串&#xff0c;字符串需要有引号。是(string)> void自定义成员函数的方法…

Spring Transaction 指定事务管理器问题

一&#xff0c;单个数据源&#xff0c;单个事务管理器与Transactional默认事务管理器名称不一致问题 在平时代码中使用声明性事务时&#xff0c;直接在方法上面加注解即可&#xff0c;如下 Transactional(rollbackFor Exception.class) 并没有指定事务管理器&#xff0c;为…

人工智能|推荐系统——搜索引擎广告

原文题目 Dark sides of artificial intelligence: The dangers of automated decision-making in search engine advertising(JASIST,2023) 人工智能的阴暗面:搜索引擎广告自动决策的危险 摘要 随着人工智能应用的日益广泛,搜索引擎供应商越来越多地要求广告商使用基于机…

Linux内核之debugfs_create_dir与debugfs_create_file实例与调用栈流程(三十二)

简介&#xff1a; CSDN博客专家&#xff0c;专注Android/Linux系统&#xff0c;分享多mic语音方案、音视频、编解码等技术&#xff0c;与大家一起成长&#xff01; 优质专栏&#xff1a;Audio工程师进阶系列【原创干货持续更新中……】&#x1f680; 优质专栏&#xff1a;多媒…

Flink集群主节点JobManager启动分析

1.概述 JobManager 是 Flink 集群的主节点&#xff0c;它包含三大重要的组件&#xff1a; ResourceManager Flink集群的资源管理器&#xff0c;负责slot的管理和申请工作。 Dispatcher 负责接收客户端提交的 JobGraph&#xff0c;随后启动一个Jobmanager&#xff0c;类似 Yarn…

动态内存管理+柔性数组

动态内存存在的意义 C语言是一种过程式编程语言&#xff0c;提供了底层访问能力和丰富的功能&#xff0c;广泛应用于操作系统、嵌入式系统、硬件驱动程序等领域。C语言的动态内存管理主要是通过malloc()、calloc()、realloc()和free()这几个标准库函数来实现的。 理解动态内存…

图论- 最小生成树

一、最小生成树-prim算法 1.1 最小生成树概念 一幅图可以有很多不同的生成树&#xff0c;比如下面这幅图&#xff0c;红色的边就组成了两棵不同的生成树&#xff1a; 对于加权图&#xff0c;每条边都有权重&#xff08;用最小生成树算法的现实场景中&#xff0c;图的边权重…

151 shell编程,正则表达式,在C语言中如何使用正则表达式

零&#xff0c;坑点记录&#xff1a;bash 和 dash 的区别&#xff0c;导致的坑点 查看当前用的shell 是啥&#xff0c;用的是/bin/bash hunandedehunandede-virtual-machine:~$ echo $SHELL /bin/bash 当shell 脚本运行的时候&#xff08;后面会学到方法&#xff0c;这里是最…

什么是搜索引擎(SEO)爬虫它们是如何工作的?

什么是搜索引擎&#xff08;SEO&#xff09;爬虫&它们是如何工作的&#xff1f; 你的网站上有蜘蛛&#x1f577;️。别抓狂&#xff01;我说的不是真正的八条腿的蜘蛛&#x1f577;️。 我指的是搜索引擎优化爬虫。他们是实现SEO的机器人。每个主要的搜索引擎都使用爬虫来…

蓝队面经(一)

蓝队面经(一) 文章目录 蓝队面经(一)入侵排查思路windows入侵排查思路Linux入侵排查思路 Linux 如何查看登录日志Windows 和 Linux 的日志文件放在哪里&#xff1f;WindowsLinux Linux 常用排查命令有哪些&#xff1f;Linux 的 Selinux 是什么&#xff1f;如何设置 Selinux&…

第十二章:预处理命令

文章目录 第十二章&#xff1a;预处理命令宏定义无参宏定义带参数的宏定义 文件包含处理 第十二章&#xff1a;预处理命令 作用&#xff1a;由编译预处理程序对程序中的特殊命令作出解释&#xff0c;以产生新的源程序对其进行正式编译 C语言与其他语言的重要区别就是可以使用预…

前端bugs

问题&#xff1a; Failed to load plugin typescript-eslint declared in package.json eslint-config-react-app#overrides[0]: Cannot find module eslint/package.json 解决&#xff1a; google了一晚上还得是chatgpt管用 运行以下命令【同时还要注意项目本身使用的Node版…

Windows 远程访问 Ubuntu Desktop - 虚拟网络控制台 (Virtual Network Console,VNC)

Windows 远程访问 Ubuntu Desktop - 虚拟网络控制台 [Virtual Network Console&#xff0c;VNC] References 1. Desktop Sharing 2. Desktop Sharing Preferences 勾选 允许其他人查看您的桌面 勾选 要求远程用户输入此密码 取消勾选 必须为对本机器的每次访问进行确定 3. 虚拟…

【QT学习】1.qt初识,创建qt工程,使用按钮,第一个交互按钮

1.初识qt--》qt是个框架&#xff0c;不是语言 1.学习路径 一 QT简介 &#xff0c;QTCreator &#xff0c;QT工程 &#xff0c;QT的第一个程序&#xff0c;类&#xff0c;组件 二 信号与槽 三 对话框 四 QT Desiner 控件 布局 样式 五 事件 六 GUI绘图 七 文件 八 …

js的一些底层

数据类型 按照存储方式&#xff0c;JavaScript的数据类型可以分为两种&#xff0c;原始数据类型&#xff08;原始值&#xff09;和引用数据类型&#xff08;引用值&#xff09;。 原始数据类型目前有六种&#xff0c;包括Number、String、Boolean、Null、Undefined、Symb…