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

这篇具有很好参考价值的文章主要介绍了【动态规划】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);
	}

	
}

【动态规划】1223. 掷骰子模拟,# 算法题,动态规划,算法,c++,力扣,随机数,约束,序列

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步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. 掷骰子模拟,# 算法题,动态规划,算法,c++,力扣,随机数,约束,序列文章来源地址https://www.toymoban.com/news/detail-852482.html

到了这里,关于【动态规划】1223. 掷骰子模拟的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法】力扣【动态规划,LCS】1143. 最长公共子序列

    1143. 最长公共子序列 本文是对 LCS 这一 动态规划 模型的整理,以力扣平台上的算法题1143:最长公共子序列为模板题进行解析。 该题目要求计算两个字符串的最长公共子序列(Longest Common Subsequence,简称LCS)的长度。字符串的子序列是指在不改变字符顺序的情况下,通过删去

    2024年01月17日
    浏览(60)
  • SM2签名算法中随机数K的随机性对算法安全的影响

            一、构造如下SM2签名算法过程1         Sig1 r1 =         F2BFC778C66127C74E3613FAA1AB6E207059740B317597A78BBFCDF58AED0A51         Sig1 s1 = 4FC719D00334CCC23098036DEEAA71DB464A076EFA79283389D3414D70659E88         私钥d = B3124DC843BB8BA61F035A7D0938251F5DD4CBFC96F5453B130D890A1CDBAE32         公钥

    2024年02月03日
    浏览(55)
  • 随机数算法,SQL

    记录 id      权重 1       5 2       10 3       50 4      100 找权重最大的那个值,调用rand()函数,它会随机生成一个0-1的值 然后 rand * 100 得出一个随机值  它的范围  0 =  随机值   100 例如本次随机值为2,那么找到 大于2的所有记录,然后升序 此时查询结果为 2     

    2024年02月09日
    浏览(35)
  • 【算法思考记录】动态规划入门!力扣2606. 找到最大开销的子字符串【Python3、动态规划】

    原题链接 动态规划(Dynamic Programming,简称 DP)是一种通过将原问题分解为相互重叠的子问题并只解决一次的方法来解决问题的算法优化技术。动态规划通常用于优化递归问题,通过存储子问题的解来避免重复计算,从而显著提高算法的效率。 动态规划的基本思想是将原问题

    2024年02月03日
    浏览(44)
  • 算法50:动态规划专练(力扣514题:自由之路-----4种写法)

    题目: 力扣514 : 自由之路  . - 力扣(LeetCode) 题目的详细描述,直接打开力扣看就是了,下面说一下我对题目的理解: 事例1: 1. ring的第一个字符默认是指向12点方向的,这一点很重要 2. key的第一个字符为g,而ring中首字符和末尾字符都为g。因此,必然存在选择首字符的g还

    2024年04月15日
    浏览(30)
  • CUDA 的随机数算法 API

    参考自 Nvidia cuRand 官方 API 文档 如下是是在 dropout 优化中手写的 uniform_random 的 Kernel: 我们首先来看 curand_init 函数的签名和语义: 给定相同的seed、sequence、offset 参数下, curand_init 会保证产生相同的其实状态 state。另外此函数会在调用 2^67 ⋅ sequence + offset 次 cu_rand API 之后「

    2024年02月03日
    浏览(45)
  • 掷骰子(从暴力搜索 到 记忆化搜索 到 动态规划)

    LeetCode上的 掷骰子模拟 题目描述通常如下: 题目:掷骰子模拟(Simulation of Dice Rolling) 原题链接 描述: 有一个骰子模拟器,每次投掷时都会生成一个1到6的随机数。不过,在使用这个模拟器时有一个约束条件:连续掷出数字i的次数不能超过rollMax[i](其中i从1开始编号)。

    2024年03月19日
    浏览(63)
  • 【算法】力扣【动态规划、状态机】309. 买卖股票的最佳时机含冷冻期

    309. 买卖股票的最佳时机含冷冻期 本文介绍解决力扣平台上第309号问题——“买卖股票的最佳时机含冷冻期”的算法。这是一个中等难度的问题,其核心是通过设计一个算法来计算在给定的股票价格数组 prices 下,能够获取的最大利润。股票价格数组 prices 中的每个元素 pric

    2024年01月18日
    浏览(49)
  • 力扣算法刷题Day39|动态规划:不同路径 I&II

    力扣题目:#62.不同路径 刷题时长:参考题解后10min 解题方法:动规 复杂度分析 时间O(m*n) 空间O(m*n) 问题总结 初始化二维数组的python语法:i 对应 m,j 对应n 二维遍历顺序,从上到下从左到右通过两层for循环实现,其中startindex应为1 本题收获 动规思路 确定dp数组及下标的含义

    2024年02月12日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包