2021-08-18 2024-10-05 problem 1 分钟读完 (大约187个字) 0次访问LC552. 学生出勤记录 II题目链接: 题解 动态规划,定义 dp[n][2][3],分别代表长度为 n,包含几个 A,末尾有几个 L 的方案数,转移的时候仔细点就可以。 参考代码 123456789101112131415161718192021222324252627282930313233343536373839404142/* * @lc app=leetcode.cn id=552 lang=cpp * * [552] 学生出勤记录 II */// @lc code=startclass Solution {public: int checkRecord(int n) { long long dp[123456][2][3]; int mod = 1e9+7; memset(dp, 0, sizeof dp); dp[0][0][0] = 1; for (int i=1;i<=n;i++) { // no A dp[i][0][0] = (dp[i][0][0] + dp[i-1][0][0] + dp[i-1][0][1] + dp[i-1][0][2])%mod; dp[i][0][1] = (dp[i][0][1] + dp[i-1][0][0])%mod; dp[i][0][2] = (dp[i][0][2] + dp[i-1][0][1])%mod; // A dp[i][1][0] = (dp[i][1][0] + dp[i-1][1][0] + dp[i-1][0][0] + dp[i-1][0][1] + dp[i-1][0][2]+ dp[i-1][1][1] + dp[i-1][1][2])%mod; dp[i][1][1] = (dp[i][1][1] + dp[i-1][1][0])%mod; dp[i][1][2] = (dp[i][1][2] + dp[i-1][1][1])%mod; } long long ans = 0; for (int i=0;i<2;i++) { for(int j=0;j<3;j++) { ans = (ans + dp[n][i][j]) % mod; } } return ans % mod; }};// @lc code=end LC552. 学生出勤记录 IIhttps://blog.xiang578.com/problem/lc552.html作者Ryen Xiang发布于2021-08-18更新于2024-10-05许可协议 LeetCode, Dynamic Programming, Problems