---
# System prepended metadata

title: 0552. Student Attendance Record II
tags: [Leetcode, Dynamic Programming, Hard]

---

# 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
```j```表示这个数列里末尾连续出现late的次数，显然对于一个valid的数列，```j```的范围只能是0和1和2
## Code
```java=
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) ;
    }
}
```