【动态规划】【矩阵快速幂】【滚动向量】C++算法552. 学生出勤记录 II

这篇具有很好参考价值的文章主要介绍了【动态规划】【矩阵快速幂】【滚动向量】C++算法552. 学生出勤记录 II。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

作者推荐

视频算法专题

本文涉及知识点

动态规划汇总
矩阵快速幂 滚动向量

本题其它解法

【矩阵快速幂】封装类及测试用例及样例

LeetCode552. 学生出勤记录 II

可以用字符串表示一个学生的出勤记录,其中的每个字符用来标记当天的出勤情况(缺勤、迟到、到场)。记录中只含下面三种字符:
‘A’:Absent,缺勤
‘L’:Late,迟到
‘P’:Present,到场
如果学生能够 同时 满足下面两个条件,则可以获得出勤奖励:
按 总出勤 计,学生缺勤(‘A’)严格 少于两天。
学生 不会 存在 连续 3 天或 连续 3 天以上的迟到(‘L’)记录。
给你一个整数 n ,表示出勤记录的长度(次数)。请你返回记录长度为 n 时,可能获得出勤奖励的记录情况 数量 。答案可能很大,所以返回对 109 + 7 取余 的结果。
示例 1:
输入:n = 2
输出:8
解释:
有 8 种长度为 2 的记录将被视为可奖励:
“PP” , “AP”, “PA”, “LP”, “PL”, “AL”, “LA”, “LL”
只有"AA"不会被视为可奖励,因为缺勤次数为 2 次(需要少于 2 次)。
示例 2:
输入:n = 1
输出:3
示例 3:
输入:n = 10101
输出:183236316
提示:
1 <= n <= 105

动态规划

时间复杂度: O(n)
计算第k天,只需要知道第k-1天的情况,所以可以用滚动向量。
注意: 连续迟到,值包括迟到,不包括缺勤。虽然缺勤更严重。

动态规划的细节,方便检查

动态规划的状态表示 pre[i][j]表示,第k-1天,缺勤i次,i-1天起,连续迟到j天的可能数量。
动态规划的转移方程 见下文
动态规划的初始状态 pre[0][0]=1
动态规划的填表顺序 天数k从小到大,确保动态规划的无后效性
动态规划的返回值 pre[i][j]的和

动态规划的转移方程

今天正常(到场):不淘汰,缺勤数量不边,连续迟到清0。
今天缺勤:淘汰已经缺勤1次的。缺勤次数+1,连续迟到清0。
今天迟到:淘汰已经迟到2次的。缺勤次数不边,迟到次数+1。

代码

核心代码

class Solution {
public:
	int checkRecord(int n) {
		vector<vector<C1097Int<>>> pre(2, vector<C1097Int<>>(3));
		pre[0][0] = 1;//缺勤0次,结尾迟到0次
		while(n--)
		{
			vector<vector<C1097Int<>>> dp(2, vector<C1097Int<>>(3));
			//处理到场
			for (int i = 0; i < 2; i++)
			{
				dp[i][0] += std::accumulate(pre[i].begin(), pre[i].end(), C1097Int<>());
			}
			//处理缺勤
			dp[1][0] += std::accumulate(pre[0].begin(), pre[0].end(), C1097Int<>());
			//处理迟到
			for (int i = 0; i < 2; i++)
			{
				for (int j = 0; j < 2; j++)
				{
					dp[i][j + 1] += pre[i][j];
				}
			}
			pre.swap(dp);
		}
		C1097Int<> biRet = std::accumulate(pre[0].begin(), pre[0].end(), C1097Int<>())
			+ std::accumulate(pre[1].begin(), pre[1].end(), C1097Int<>());
		return biRet.ToInt();
	}
};

测试用例

template<class T>
void Assert(const T& t1, const T& 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;
	{
		Solution sln;
		n = 2;
		auto res = sln.checkRecord(n);
		Assert(8, res);
	}
	{
		Solution sln;
		n = 1;
		auto res = sln.checkRecord(n);
		Assert(3, res);
	}
	{
		Solution sln;
		n = 10101;
		auto res = sln.checkRecord(n);
		Assert(183236316, res);
	}
}

2023年1月

class CBigMath
{
public:
static void AddAssignment(int* dst, const int& iSrc)
{
*dst = (*dst + iSrc) % s_iMod;
}

 static void AddAssignment(int* dst, const int& iSrc, const int& iSrc1)
 {
	 *dst = (*dst + iSrc) % s_iMod;
	 *dst = (*dst + iSrc1) % s_iMod;
 }

 static void AddAssignment(int* dst, const int& iSrc, const int& iSrc1, const int& iSrc2)
 {
	 *dst = (*dst + iSrc) % s_iMod;
	 *dst = (*dst + iSrc1) % s_iMod;
	 *dst = (*dst + iSrc2) % s_iMod;
 }

 static void SubAssignment(int* dst, const int& iSrc)
 {
	 *dst = (s_iMod - iSrc + *dst) % s_iMod;
 }
 static int Add(const int& iAdd1, const int& iAdd2)
 {
	 return (iAdd1 + iAdd2) % s_iMod;
 }
 static int Mul(const int& i1, const int& i2)
 {
	 return((long long)i1 *i2) % s_iMod;
 }

private:
static const int s_iMod = 1000000007;
};

class Solution {
public:
int checkRecord(int n) {
//preDp[i][j]表示缺勤i天,最后一天连续j天迟到
vector<vector> preDp;
preDp.assign(2, vector(3));
preDp[0][0] = 1;
for (int i = 0; i < n; i++)
{
vector<vector> dp;
dp.assign(2, vector(3));
//正常通勤
CBigMath::AddAssignment(&dp[0][0], preDp[0][0], preDp[0][1], preDp[0][2]);
CBigMath::AddAssignment(&dp[1][0], preDp[1][0], preDp[1][1], preDp[1][2]);
//缺勤
CBigMath::AddAssignment(&dp[1][0], preDp[0][0], preDp[0][1], preDp[0][2]);
//迟到
for (int j = 0; j < 2; j++)
{
for (int k = 0; k < 2; k++)
{
CBigMath::AddAssignment(&dp[j][k + 1], preDp[j][k]);
}
}
preDp.swap(dp);
}

	 int iRet = 0;
	 for (int i = 0; i < preDp.size(); i++)
	 {
		 for (int j = 0; j < preDp[i].size(); j++)
		 {
			 CBigMath::AddAssignment(&iRet, preDp[i][j]);
		 }
	 }
	 return iRet;
 }

};

【动态规划】【矩阵快速幂】【滚动向量】C++算法552. 学生出勤记录 II,# 算法题,数据结构与算法,算法,动态规划,矩阵,c++,leetcode,滚动向量,出勤

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步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++**实现。

【动态规划】【矩阵快速幂】【滚动向量】C++算法552. 学生出勤记录 II,# 算法题,数据结构与算法,算法,动态规划,矩阵,c++,leetcode,滚动向量,出勤文章来源地址https://www.toymoban.com/news/detail-791672.html

到了这里,关于【动态规划】【矩阵快速幂】【滚动向量】C++算法552. 学生出勤记录 II的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【动态规划】矩阵链乘法——算法设计与分析

    对于矩阵 U p × q U_{ptimes q} U p × q ​ 和 V q × r V_{qtimes r} V q × r ​ , Z p × r = U V Z_{ptimes r}=UV Z p × r ​ = U V ,共需计算 p q r pqr pq r 次标量乘法,时间复杂度为 Θ ( p q r ) Theta (pqr) Θ ( pq r ) 矩阵乘法满足结合律,即 ( U V ) W = U ( V W ) (UV)W=U(VW) ( U V ) W = U ( VW ) ,选择不同的结合

    2024年02月03日
    浏览(61)
  • 动态规划之矩阵连乘问题C++版

    算法总体思想          动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题         但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时,有些子问题被重复计算了许多次。        

    2024年01月16日
    浏览(42)
  • 【力扣·每日一题】2645. 构造有效字符串的最小插入数(动态规划 贪心 滚动数组优化 C++ Go)

    题目链接 给你一个字符串 word ,你可以向其中任何位置插入 “a”、“b” 或 “c” 任意次,返回使 word 有效 需要插入的最少字母数。 如果字符串可以由 “abc” 串联多次得到,则认为该字符串 有效 。 提示: 1 = w o r d . l e n g t h = 50 1 = word.length = 50 1 = w or d . l e n g t h = 50 w

    2024年01月16日
    浏览(48)
  • 《算法导论》学习(十八)----动态规划之矩阵链乘(C语言)

    本文主要讲解了动态规划中的矩阵链乘问题:给定一个矩阵链,得到它的最小代价计算次序。给出了动态规划方案的分析,并且给出了C语言实现。 给定一个n个矩阵的序列(矩阵链) A 1 , A 2 , A 3 , A 4 , . . . , A n A_1,A_2,A_3,A_4,...,A_n A 1 ​ , A 2 ​ , A 3 ​ , A 4 ​ , ... , A n ​ ,现在

    2024年02月06日
    浏览(44)
  • 动态规划算法学习一:DP的重要知识点、矩阵连乘算法

    三部曲如下三步: 基本原则:“空间换时间” 存储重复子问题的解,减少运算时间 底层运算:“表格操作” 用表格存储子问题的解 实现路线:“子问题划分、自底向上求解” 利用表格中存储的子问题的解,求上一层子问题的解。 矩阵连乘计算次序 可以用 加括号的方式

    2024年02月09日
    浏览(39)
  • 动态规划2:算法考试矩阵连乘问题(超详细手写过程)

                                      更多期末复习笔记欢迎访问我的博客: Miuuu · 语雀​​​​​​​ 动态规划理论基础:(6条消息) 动态规划1:动态规划的入门初学理论基础_黑色柳丁Angel的博客-CSDN博客 矩阵连乘问题是我在算法课接触的第一个动态规划问题

    2023年04月08日
    浏览(39)
  • 【算法思维】-- 动态规划(C++)

    OJ须知: 一般而言,OJ在1s内能接受的算法时间复杂度:10e8 ~ 10e9之间 (中值5*10e8) 。在竞赛中, 一般认为计算机1秒能执行 5*10e8 次计算 。 时间复杂度 取值范围 o(log2n) 大的离谱 O(n) 10e8 O(nlog(n)) 10e6 O(nsqrt(n))) 10e5 O(n^2) 5000 O(n^3) 300 O(2^n) 25 O(3^n) 15 O(n!) 11 时间复杂度排序: o(1

    2024年02月02日
    浏览(45)
  • 最大子矩阵(openjudge noi-2.6基本算法之动态规划-1768)

    来源 OpenJudge - 1768:最大子矩阵 题目描述 已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵,你的任务是找到最大的非空(大小至少是1 * 1)子矩阵。 比如,如下4 * 4的矩阵  0        -2        -7        0  9         2        -6        2 -4      

    2024年04月26日
    浏览(39)
  • C++动态规划-线性dp算法

    莫愁千里路 自有到来风 CSDN 请求进入专栏                                    X 是否进入《 C++ 专栏》? 确定 目录  线性dp简介 斐波那契数列模型  第N个泰波那契数 思路: 代码测试:  三步问题 思路: 代码测试: 最小花费爬楼梯 思路: 代码测试:  路径问题 数字三

    2024年02月19日
    浏览(46)
  • 【动态规划】C++算法:403.青蛙过河

    视频算法专题 动态规划汇总 一只青蛙想要过河。 假定河流被等分为若干个单元格,并且在每一个单元格内都有可能放有一块石子(也有可能没有)。 青蛙可以跳上石子,但是不可以跳入水中。 给你石子的位置列表 stones(用单元格序号 升序 表示), 请判定青蛙能否成功过

    2024年01月17日
    浏览(47)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包