Hồ sơ điểm danh II (Student Attendance Record II) trong C++

Đếm số chuỗi độ dài n trên {A,L,P} thỏa: tối đa 1 'A', không có "LLL". Trả về modulo 1e9+7.

Ví dụ

n=2 → 8 (PP, AP, PA, LP, PL, AL, LA, LL).

DP trạng thái

Theo dõi 5 trạng thái kết thúc: P, A, L, AP, AL (không có LL vì đã xử lý trong chuyển trạng thái). Chuyển trạng thái O(n).

Chương trình C++

#include <bits/stdc++.h> 
using namespace std;
using lli = long long;
const lli MOD = 1e9+7;

class Solution {
    lli add(lli a, lli b){ return (a%MOD + b%MOD)%MOD; }
public:
    int checkRecord(int n) {
        vector<lli> P(n+1), A(n+1), L(n+1), AP(n+1), AL(n+1);
        if(n==1) return 3;
        P[0]=P[1]=1; P[2]=3;
        A[0]=A[1]=1; A[2]=2;
        L[0]=L[1]=1; L[2]=3;
        AP[0]=AP[1]=1; AP[2]=2;
        AL[0]=AL[1]=1; AL[2]=2;
        for(int i=3;i<=n;i++) {
            P[i] = add(add(P[i-1], A[i-1]), L[i-1]);
            L[i] = add(add(P[i-1], P[i-2]), add(A[i-1], A[i-2]));
            A[i] = add(AL[i-1], AP[i-1]);
            AL[i] = add(AP[i-1], AP[i-2]);
            AP[i] = add(AP[i-1], AL[i-1]);
        }
        return add(add(P[n], L[n]), A[n]);
    }
};

int main() {
    Solution ob;
    cout << ob.checkRecord(3); // 19
    return 0;
}