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

本文主要是介绍【动态规划】【矩阵快速幂】【滚动向量】C++算法552. 学生出勤记录 II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

作者推荐

【动态规划】458:可怜的小猪

本题其它解法

【矩阵快速幂】封装类及测试用例及样例预计2024年1月15（周一7:00）发布

涉及知识点

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

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 <= 10⁵

动态规划

时间复杂度: 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;}

};

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛