力扣题库-掷骰子模拟详细解析

题目如下:

有一个骰子模拟器会每次投掷的时候生成一个 1 到 6 的随机数。

不过我们在使用它时有个约束,就是使得投掷骰子时,连续 掷出数字 i 的次数不能超过 rollMax[i]i 从 1 开始编号)。

现在,给你一个整数数组 rollMax 和一个整数 n,请你来计算掷 n 次骰子可得到的不同点数序列的数量。

假如两个序列中至少存在一个元素不同,就认为这两个序列是不同的。

由于答案可能很大,所以请返回 模 10^9 + 7 之后的结果。

限制如下

  • 1 <= n <= 5000
  • rollMax.length == 6
  • 1 <= rollMax[i] <= 15

解析如下:

在不考虑rollMax 限制情况下

若第1次投掷1~6,连续1次点数相同,则每个点数各有1种,即d[1][i][1] = 1(初始值),定义i为

                第一次可能投掷出的点数,X为第一次已经投掷出的点数,则第一次投掷结果表示为  X 

若第2次投掷1~6,连续2次点数相同,则每个点数各有1种,即d[2][i][2] = 1,i为第二次可能投掷

                出的点数,Y为第二次已经投掷出的点数,则两次投掷出的结果表示为 XY,且X=Y,

                则d[2][i][2] = d[1][i][1]

                投掷1~6,连续1次点数相同, 则两次投掷出的结果表示为 XY,且X != Y,在Y确定时,

                只需考虑前一次的情况,即X的值,X有6-1种选择,即d[2][i][1] = d[1][j][1] * 5 ,此处

                *5表示第一次投掷d[1][i][1] 6种情况 减去X=Y这种情况的累加,

                d[2][i][1] = d[1][a][1]+d[1][b][1]+d[1][c][1]+d[1][d][1]+d[1][e][1]

若第3次投掷1~6,连续3次点数相同, 则每个点数各有1种,即d[3][i][3] = 1,i为第三次可能投掷

                出的点数,Z为第三次已经投掷出的点数,则三次投掷出的结果表示为 XYZ,X=Y=Z,

                在Z确定时,只需要考虑前两次的投掷情况,即XY的值,因为X=Y,所以只考虑第二次

                投掷1~6,连续2次点数相同的情况即d[2][i][2]的情况,又因为Z = Y,所以Y只有一种选

                择,所以d[3][i][3] = d[2][i][2] = d[1][i][1]

                投掷1~6,连续2次点数相同, 则三次投掷出的结果表示为 XYZ,且Z = Y != X,在Z

                确定时,只需要考虑前两次的投掷情况,即XY的值,因为Y != X,所以只考虑第二次

                投掷1~6,连续1次点数相同的情况即d[2][i][1]的情况,

                又因为Z = Y,所以Y只有一种选择,所以d[3][i][2] = d[2][i][1]

                投掷1~6,连续1次点数相同,则三次投掷出的结果表示为 XYZ,且Z != Y,Y与X可相等

                可不等,

                先考虑Y != X情况,在Z确定时,只需要考虑前两次的投掷情况,即XY的值,因为Y !=                 X,所以只考虑第二次投掷1~6,连续1次点数相同的情况即d[2][i][1]的情况,

                又因为Z != Y,所以Y有6-1种选择,

                即d[3][i][1] =  d[2][i][1] * 5 = d[2][a][1]+d[2][b][1]+d[2][c][1]+d[2][d][1]+d[2][e][1]

                再考虑Y=X情况,在Z确定时,只需要考虑前两次的投掷情况,即XY的值,

                因为Y = X,所以只考虑第二次投掷1~6,连续2次点数相同的情况即d[2][i][2]的情况,

                又因为Z != Y,所以Y有6-1种选择,

                即d[3][i][1] = d[2][i][2] * 5 = d[2][a][2]+d[2][b][2]+d[2][c][2]+d[2][d][2]+d[2][e][2]注意从

                此处开始就需要考虑rollMax 的影响,暂时先忽略

                将上述两种情况相加可得:d[3][i][1] = d[2][a][1]+d[2][b][1]+d[2][c][1]+d[2][d][1]+d[2][e][1] + d[2][a][2]+d[2][b][2]+d[2][c][2]+d[2][d][2]+d[2][e][2],可以转变为下面的代码

d[3][i][1] = 0;
for(int v = 1; v <= 6; v++)
{for(int k = 1; k <= 2; k++){if(v != i){d[3][i][1] += d[2][v][k];}}
}

由上述几种投掷情况,可以发现,连续1次点数相同情况特殊,需要找上一次投掷的所用情况中排除,而超过1次点数相同情况只需要找上一次投掷中对应次数-1的结果即可,总结如下

第n次投掷1~6,连续1次点数相同的即d[n][i][1]的值为第n-1次投掷连续1次,2次到n-1次点数相同的所有情况减去每种情况下点数与i相同的情况的总和,如下

for(int v = 1; v <= 6; v++)
{for(int k = 1; k <= n - 1; k++){if(v != i){d[n][i][1] += d[n-1][v][k];}}
}
带入n = 2,结果正确

第n次投掷1~6,连续k次点数相同(k>1)的即d[n][i][k]的值第n-1次投掷连续k-1次点数相同的6种情况中第n-1次投掷与第n次投掷结果相同的一种情况,即d[n][i][k] = d[n - 1][i][k-1]

由上述总结可以得到如下的忽略rollMax 的代码

const int MOD = 1000000007;int DieSimulator2(int n)
{//状态 d[i][j][k] 表示已经完成了 i 次掷骰子,第 i 次掷的是 j,并且已经连续掷了 k 次 j 的方案数。//投掷从1开始算,所以为 n+1int[][][] d = new int[n + 1][][];for (int i = 0; i <= n; i++){d[i] = new int[6][];for (int j = 0; j < 6; j++){//此处的16表示最多连续15次,由1 <= rollMax[i] <= 15得到d[i][j] = new int[16];}}//第一次投掷出且连续掷出j的方案数只能是1,用0~5来代替投掷出1~6的点数for (int j = 0; j < 6; j++){d[1][j][1] = 1;}//第一次投掷结果已知,从第二次开始for(int i = 2; i <= n; i++){//本次投掷的结果for(int j = 0; j < 6; j++){//本次投掷的连续次数for(int k = 1; k <= n; k++){if(k != 1){//本次投掷连续次数不为1,结果为i-1次投掷中,结果为j且连续k-1次的情况d[i][j][k] += d[i - 1][j][k - 1];d[i][j][k] %= MOD;}else{//本次投掷连续次数为1,结果为i-1次投掷中,结果不为j,连续次数随意的情况总和//p为i-1次投掷的结果for (int p = 0; p < 6; p++){//lk为i-1次投掷结果的连续次数,lk不能超过ifor (int lk = 1; lk < i; lk++){//j与p不等情况的累加if(j != p){d[i][j][1] += d[i - 1][p][lk]; d[i][j][1] %= MOD;}}}}}}}int res = 0;for (int j = 0; j < 6; j++){for (int k = 1; k <= n; k++){res = (res + d[n][j][k]) % MOD;}}return res;
}

现在开始考虑rollMax的限制条件,替换其实很简单,就是在对投掷点数的连续次数的循环上加上限制即可,比如在计算本次连续投掷次数时 for(int k = 1; k <= n; k++) //本次投掷的连续次数原先的限制为连续次数不能超过总投掷次数,改为 for(int k = 1; k <= rollMax[j]; k++),不能超过rollMax对应值限制的次数即可,以及在计算本次投掷连续次数为1时,使用上一次投掷情况的地方 for (int lk = 1; lk < i; lk++) //lk为i-1次投掷结果的连续次数,原限制为连续次数不能超出i-1的投掷次数,改为for (int lk = 1; lk <= rollMax[p]; lk++),变为不能超过rollMax上次投掷值对应限制的次数即可,最后在计算总数时,一样加上限制即可。

添加限制后的代码如下

const int MOD = 1000000007;public int DieSimulator(int n, int[] rollMax)
{//状态 d[i][j][k] 表示已经完成了 i 次掷骰子,第 i 次掷的是 j,并且已经连续掷了 k 次 j 的方案数。//投掷从1开始算,所以为 n+1int[][][] d = new int[n + 1][][];for (int i = 0; i <= n; i++){d[i] = new int[6][];for (int j = 0; j < 6; j++){//此处的16表示最多连续15次,由1 <= rollMax[i] <= 15得到d[i][j] = new int[16];}}//第一次投掷出且连续掷出j的方案数只能是1,用0~5来代替投掷出1~6的点数for (int j = 0; j < 6; j++){d[1][j][1] = 1;}//第一次投掷结果已知,从第二次开始for(int i = 2; i <= n; i++){//本次投掷的结果for(int j = 0; j < 6; j++){//本次投掷的连续次数for(int k = 1; k <= rollMax[j]; k++){if(k != 1){//本次投掷连续次数不为1,结果为i-1次投掷中,结果为j且连续k-1次的情况d[i][j][k] += d[i - 1][j][k - 1];d[i][j][k] %= MOD;}else{//本次投掷连续次数为1,结果为i-1次投掷中,结果不为j,连续次数随意的情况总和//p为i-1次投掷的结果for (int p = 0; p < 6; p++){//lk为i-1次投掷结果的连续次数for (int lk = 1; lk <= rollMax[p]; lk++){//j与p不等情况的累加,且上次投掷连续次数不能超过当前投掷次数if(j != p && lk < i){d[i][j][1] += d[i - 1][p][lk];d[i][j][1] %= MOD;}}}}}}}int res = 0;for (int j = 0; j < 6; j++){for (int k = 1; k <= rollMax[j]; k++){res = (res + d[n][j][k]) % MOD;}}return res;
}

到这,解析就结束了,当然还有优化空间,但这已经石是我自己研究出来的结果了

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

ArcMap 分析栅格欧式分配、构建趋势面、插值模型精度等功能操作

ArcMap 分析栅格欧式分配、构建趋势面、插值模型精度等功能操作今天进行 一、栅格欧式分配 1、对点要素进行空间分配 配置环境变量 点击确定后展示 2、对线要素进行空间分配 环境变量依然选择 road 相同&#xff0c;点击确定后展示 3、对面要素进行空间分配 环境配置与 road …

推荐在线Sql运行

SQL Fiddle 1、网址&#xff1a;SQL Fiddle - Online SQL Compiler for learning & practiceDiscover our free online SQL editor enhanced with AI to chat, explain, and generate code. Support SQL Server, MySQL, MariaDB, PostgreSQL, and SQLite.http://www.sqlfi…

MySQL 8.0 新特性汇总

文章目录 前言1. 运维管理 1.1 可持久化变量1.2 管理员端口1.3 资源组1.4 数据库粒度只读1.5 show processlist 实现方式1.6 加速索引创建速度1.7 控制连接的内存使用量1.8 克隆插件1.9 mysqldump 新增参数1.10 慢日志增强1.11 快速加列1.12 InnoDB 隐藏主键1.13 Redo 配置1.14…

使用android studio写一个Android的远程通信软件(APP),有通讯的发送和接收消息界面

以下是使用 Android Studio 基于 Java 语言编写一个简单的 Android APP 实现远程通信&#xff08;这里以 TCP 通信为例&#xff09;的代码示例&#xff0c;包含基本的通信界面以及发送和接收消息功能。 1. 创建项目 打开 Android Studio&#xff0c;新建一个 Empty Activity …

记录blender学习过程中遇到的问题

物体发射的方向不对 被发射物体&#xff08;例如一棵树&#xff09;n键看旋转归0 切换正视图 将被发射物体的局部坐标的Z轴 指向 全局方向的X轴时 并且把粒子系统设置的物体旋转勾选上 方向就对了 做倒角发现有问题 检查缩放应用、面朝向、有没有重合点&#xff08;融合点&am…

【RBF SBN READ】hadoop社区基于RBF的SBN READ请求流转

读写分离功能的背景及架构 当前联邦生产集群的各个子集群只有Active NameNode在工作,当读写任务变得繁忙的时候,只有一个Active负责处理的话,此时集群的响应和处理能力业务侧感知会明显下降,为此,我们将引入Observer架构,实现读写功能的分离,使得Active只负责写请求,而…

01-Chromedriver下载与配置(mac)

下载地址&#xff1a; 这里我用的最后一个&#xff0c;根据自己chrome浏览器选择相应的版本号即可 ChromeDriver官网下载地址&#xff1a;https://sites.google.com/chromium.org/driver/downloads ChromeDriver官网最新版下载地址&#xff1a;https://googlechromelabs.git…

MySQL——buffer poll

为什么要有buffer poll&#xff1f; 如果没有buffer poll&#xff0c;每次读取数据的时候都是从磁盘上读的&#xff0c;这样效率是很差的的。 所以有了提高效率的方式&#xff0c;就加上了一个缓存——buffer poll 所以&#xff0c;当我们读取数据的时候就有以下的方式 当读…

重磅升级:OpenAI o1模型上手实测,从芯片架构分析到象棋残局判断的全能表现

引言 昨日&#xff0c;在圣诞节系列发布会的第一天&#xff0c;OpenAI终于给我们带来了令人振奋的更新&#xff0c;这些更新有望塑造AI互动的未来。备受期待的OpenAI o1正式版的推出&#xff0c;标志着ChatGPT体验的重大进化&#xff0c;宣告了AI驱动应用新时代的开始。o1现已可…

oracle之用户的相关操作

&#xff08;1&#xff09;创建用户(sys用户下操作) 简单创建用户如下&#xff1a; CREATE USER username IDENTIFIED BY password; 如果需要自定义更多的信息&#xff0c;如用户使用的表空间等&#xff0c;可以使用如下&#xff1a; CREATE USER mall IDENTIFIED BY 12345…

IDL学习笔记(四)MODIS数据处理。MODIS数据介绍,以及Swath数据处理

MODIS数据处理 MODIS传感器介绍MODIS 数据产品Swath 数据Grid 数据 MODIS Swath 数据重投影对应ENVI接口UTM重投影 重投影后数据由ENVI版本&#xff0c;修改为GeoTiff格式。根据经纬度&#xff0c;快速重投影MODIS数据 下标 和 行列号转换 MODIS传感器介绍 MODlS (Moderate Re…

pushgateway HA高可用方案

未经本人同意不得转载&#xff0c;若引用请附上原文链接。 项目使用flink来处理kafka中的无界流数据&#xff0c;采用的是flink on yarn的模式部署flink任务。最近做flink任务的监控过程中&#xff0c;踩了一些坑。下面是过程&#xff0c;只想看最终方案的直接拉到最后。 先说…

burp常用机漏洞测试理论

声明&#xff01; 学习视频来自B站up主 **泷羽sec** 有兴趣的师傅可以关注一下&#xff0c;如涉及侵权马上删除文章&#xff0c;笔记只是方便各位师傅的学习和探讨&#xff0c;文章所提到的网站以及内容&#xff0c;只做学习交流&#xff0c;其他均与本人以及泷羽sec团队无关&a…

【深度学习】手机SIM卡托缺陷检测【附链接】

一、手机SIM卡托用途 SIM卡托是用于固定和保护SIM卡的部件&#xff0c;通过连接SIM卡与手机主板的方式&#xff0c;允许设备访问移动网络&#xff0c;用户可以通过SIM卡进行通话、发送短信和使用数据服务。 二、手机SIM卡托不良影响 SIM卡接触不良&#xff0c;造成信号中断&…

【机器学习】深入解析 PCA 与三元组损失:从理论推导到实践应用

深入解析 PCA 与三元组损失&#xff1a;从理论推导到实践应用 PCA (Principal Component Analysis) 主成分分析详解1. 基本概念1.1 什么是 PCA&#xff1f;1.2 核心目标1.3 应用场景 2. 数学原理详解2.1 问题形式化2.2 数据预处理2.3 协方差矩阵的计算2.4 特征值分解2.5 最大方…

记录:ubuntu 使用chattts的过程。

你知道什么是穷人吗&#xff1f;穷人就是没钱还想学习。 git GitHub - 2noise/ChatTTS: A generative speech model for daily dialogue. 因为所以。cosyvoice&#xff0c;gpt-s . 0.先找一个目录吧。 1.命令行模式 duyichengduyicheng-computer:~/gitee$ git clone https:…

开源 - Ideal库 - Excel帮助类,ExcelHelper实现(五)

书接上回&#xff0c;我们继续来聊聊ExcelHelper的具体实现。 01、读取Excel到DataSet单元测试 在上一章我们主要讲解了读取Excel到DataSet的三个重载方法具体实现&#xff0c;还没来得及做单元测试&#xff0c;因此我们首先对这三个方法做个单元测试。具体代码如下&#xff1…

CCF-GESP 编程能力认证 C++ 七级 2024年9月份选择题详细解析

第 1 题 已知小写字母 b 的 ASCII 码为 98 &#xff0c;下列 C 代码的输出结果是&#xff08;B&#xff09;。 #include <iostream> using namespace std; int main() {char a b;a;cout << a;return 0; } A. b B. c C. 98 D. 99 【这题很简单&#xff0c;我们只…

Oceanbase离线集群部署

准备工作 两台服务器 服务器的配置参照官网要求来 服务器名配置服务器IPoceanbase116g8h192.168.10.239oceanbase216g8h192.168.10.239 这里选oceanbase1作为 obd机器 oceanbase安装包 选择社区版本的时候自己系统的安装包 ntp时间同步rpm包 联网机器下载所需的软件包 …

动手学深度学习d2l包M4芯片 gpu加速

conda创建环境 CONDA_SUBDIRosx-arm64 conda create -n ml python3.9 -c conda-forge conda env config vars set CONDA_SUBDIRosx-arm64 conda activate mlpip安装包 pip install --pre torch torchvision torchaudio --extra-index-url https://download.pytorch.org/whl/n…