# 0552. Student Attendance Record II
###### tags: `Leetcode` `Hard` `Dynamic Programming`
Link: https://leetcode.com/problems/student-attendance-record-ii/description/
## 思路
基本型I DP
有六种状态 ```dp00, dp01, dp02, dp10, dp11, dp12```
$dp_{ij}$ ```i```表示这个数列里absence出现的次数，显然对于一个valid的数列，```i```的范围只能是0和1

## Code

class Solution {
public int checkRecord(int n) {
long[] dp00 = new long[n+1];
long[] dp01 = new long[n+1];
long[] dp02 = new long[n+1];
long[] dp10 = new long[n+1];
long[] dp11 = new long[n+1];
long[] dp12 = new long[n+1];
dp00[0] = 1;
int mod = 1000000007;
for(int i=1; i<=n; i++){
dp00[i] = (dp00[i-1]+dp01[i-1]+dp02[i-1])%mod;
dp01[i] = dp00[i-1];
dp02[i] = dp01[i-1];
dp10[i] = (dp00[i-1]+dp01[i-1]+dp02[i-1]+dp10[i-1]+dp11[i-1]+dp12[i-1])%mod;
dp11[i] = dp10[i-1];
dp12[i] = dp11[i-1];
}
return (int)((dp00[n]+dp01[n]+dp02[n]+dp10[n]+dp11[n]+dp12[n])%mod) ;
}
}