文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給定一個(gè)正整數(shù) n，返回長度為 n 的所有可被視為可獎(jiǎng)勵(lì)的出勤記錄的數(shù)量。
答案可能非常大，你只需返回結(jié)果mod 10^9 + 7的值。

學(xué)生出勤記錄是只包含以下三個(gè)字符的字符串：

'A' : Absent，缺勤 'L' : Late，遲到 'P' : Present，到場(chǎng)

如果記錄不包含 多于一個(gè)'A'（缺勤）或 超過兩個(gè)連續(xù)的'L'（遲到），則該記錄被視為可獎(jiǎng)勵(lì)的。

示例 1: 輸入: n = 2 輸出: 8 解釋： 有8個(gè)長度為2的記錄將被視為可獎(jiǎng)勵(lì)： "PP" , "AP", "PA", "LP", "PL", "AL", "LA", "LL" 只有"AA"不會(huì)被視為可獎(jiǎng)勵(lì)，因?yàn)槿鼻诖螖?shù)超過一次。 注意：n 的值不會(huì)超過100000。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/student-attendance-record-ii
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

類似題目：
LeetCode 576. 出界的路徑數(shù)（動(dòng)態(tài)規(guī)劃）
LeetCode 688. “馬”在棋盤上的概率（DP）
LeetCode 935. 騎士撥號(hào)器（動(dòng)態(tài)規(guī)劃）

• 狀態(tài)壓縮，理清楚狀態(tài)如何轉(zhuǎn)移就很簡(jiǎn)單了

class Solution { public:int checkRecord(int n) {int ans = 0, mod = 1e9+7;vector<vector<long long>> dp(n, vector<long long>(13, 0));// APLL, 4個(gè)二進(jìn)制位, 表示結(jié)尾出現(xiàn)字符的情況// 8421dp[0][8] = 1; // A結(jié)尾dp[0][4] = 1; // P結(jié)尾dp[0][1] = 1; // L結(jié)尾for(int i = 1; i < n; i++) {// A結(jié)尾, 原來可能是 P,L,LL結(jié)尾dp[i][8] += (dp[i-1][4]+dp[i-1][1]+dp[i-1][2])%mod;// P結(jié)尾，原來沒有A, 原來結(jié)尾可能是 P, L, LLdp[i][4] += (dp[i-1][4]+dp[i-1][1]+dp[i-1][2])%mod;// P結(jié)尾，原來有A, 原來結(jié)尾可能是 A, P, L, LLdp[i][12] += (dp[i-1][8]+dp[i-1][12]+dp[i-1][9]+dp[i-1][10])%mod;// L結(jié)尾，原來沒有A, 原來結(jié)尾可能是 Pdp[i][1] += dp[i-1][4]%mod;// L結(jié)尾，原來有A, 原來結(jié)尾可能是 A, Pdp[i][9] += (dp[i-1][8]+dp[i-1][12])%mod;// LL結(jié)尾，原來沒有A, 原來結(jié)尾可能是 Ldp[i][2] += dp[i-1][1]%mod;// LL結(jié)尾，原來有A, 原來結(jié)尾可能是 Ldp[i][10] += dp[i-1][9]%mod;}for(int i = 1; i <= 12; i++)ans = (ans+dp[n-1][i])%mod;return ans;} };

1344 ms 441.4 MB C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關(guān)注我的公眾號(hào)（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 552. 学生出勤记录 II（动态规划）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。