552. 學生出勤記錄 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

解題思路

dp[n][i][j]表示前n天，缺勤i天，連續遲到j天的情況

狀態轉移

第n天可能產生3種情況，分別是曠課，遲到和正常出勤

• 正常出勤：正常出勤的情況可以由以下情況轉移而來（轉移而來的缺勤天數i保持相同）

1. 前一天正常出勤或者缺勤
2. 前一天連續遲到一天
3. 前一天連續遲到兩天

• 曠課：由缺勤天數為0的所有情況轉移而來

1. 前一天正常出勤
2. 前一天連續遲到一天
3. 前一天連續遲到兩天

• 遲到一天：遲到的情況可以由以下情況轉移而來（轉移而來的缺勤天數i保持相同）

1. 前一天正常出勤或者缺勤

• 遲到二天：遲到的情況可以由以下情況轉移而來（轉移而來的缺勤天數i保持相同）

1. 前一天連續遲到一天

代碼

class Solution {public int checkRecord(int n) {// 天數，曠課，遲到int[][][] dp = new int[n][2][3];dp[0][1][0]=1;dp[0][0][1]=1;dp[0][0][0]=1;int mod=1000000007;for (int i=1;i<n;i++){//------曠課--------//今天才曠課的for (int k=0;k<3;k++)dp[i][1][0]=(dp[i-1][0][k]+dp[i][1][0])%mod;// 今天遲到的for (int j=0;j<2;j++){dp[i][j][2]=dp[i-1][j][1];dp[i][j][1]=dp[i-1][j][0];}//今天沒事的for (int j=0;j<2;j++)for (int k=0;k<3;k++)dp[i][j][0]=(dp[i][j][0]+dp[i-1][j][k])%mod;}int res=0;for (int j=0;j<2;j++)for (int k=0;k<3;k++)res=(res+dp[n-1][j][k])%mod;return res;}
}