บันทึกเข้าเรียน 2 (Student Attendance Record II) ใน C++

ภาพรวมปัญหา

กำหนด n หาจำนวนบันทึกเข้าเรียนความยาว n ที่ได้รับรางวัล (rewardable) mod 1e9+7 ตัวอักษร: A=ขาด, L=สาย, P=มา ได้รางวัลถ้า: A ≤ 1 ตัว, ไม่มี L ติดกัน 3 ตัว

ตัวอย่าง

n=2 → 8 วิธี: PP, AP, PA, LP, PL, AL, LA, LL (AA ไม่ได้)

n=3 → 19 วิธี

แนวทางแก้ปัญหา (DP 5 สถานะ)

• p[i] = จำนวนสตริงความยาว i จบด้วย P (ไม่มี A)
• a[i] = จำนวนสตริงความยาว i มี A 1 ตัว จบด้วย P
• l[i] = จำนวนสตริงความยาว i จบด้วย L 1 ตัว (ไม่มี A)
• ap[i] = จำนวนสตริงความยาว i มี A 1 ตัว จบด้วย L 1 ตัว
• al[i] = จำนวนสตริงความยาว i มี A 1 ตัว จบด้วย L 2 ตัว
• Recurrence จากการต่อท้าย P, L, A

ตัวอย่างโปรแกรม

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

class Solution {
public:
    lli add(lli a, lli b) { return ((a % m) + (b % m)) % m; }
    
    int checkRecord(int n) {
        vector<int> p(n+1), a(n+1), l(n+1), ap(n+1), al(n+1);
        if(n == 1) return 3;
        
        p[0]=1; p[1]=1; p[2]=3;
        a[0]=1; a[1]=1; a[2]=2;
        l[0]=1; l[1]=1; l[2]=3;
        ap[0]=1; ap[1]=1; ap[2]=2;
        al[0]=1; 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));
}

Input

3

Output

19