552. Student Attendance Record II

Description

image-20210818221429258

image-20210818221439535

Solution

A typical finite-state machine problem + dp. Just draw a state transfer graph.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    static const int MOD = 1E9 + 7;
public:
    int checkRecord(int n) {
        long long p1, p2, l11, l21, l12, l22, a;
        p1 = l11 = a = 1;
        p2 = l12 = l21 = l22 = 0;
        for(int i = 1; i <n; i++){
            long long np1, np2, nl11, nl21, nl12, nl22, na;
            np1 = p1 + l11 + l21;
            nl11 = p1;
            nl21 = l11;
            na = p1 + l11 + l21;
            np2 = a + p2 + l12 + l22;
            nl12 = a + p2;
            nl22 = l12;
            p1 = np1%MOD;
            p2 = np2%MOD;
            l11 = nl11 %MOD;
            l12 = nl12 %MOD;
            l22 = nl22%MOD;
            l21 = nl21%MOD;
            a = na%MOD;
        }
        int res = 0;
        res = (p1 + p2 + l11 + l21 + l12 + l22 + a)%MOD;
        return res;
    }
};

image-20210818221915220