Student Attendance Record II: บันทึกการเข้าเรียนที่ได้รางวัลใน C++

ปัญหา

หาจำนวน Attendance Record ความยาว n ที่ "ได้รางวัล" (Rewardable) โดย:

• ตัวอักษร: 'A' (Absent), 'L' (Late), 'P' (Present)
• เงื่อนไข: สูงสุด 1 'A' และ ไม่มี 'L' ติดกันเกิน 2 ตัว

คำตอบ modulo 10^9 + 7

ตัวอย่าง: n=2 → 8 วิธี: PP, AP, PA, LP, PL, AL, LA, LL (เฉพาะ AA ไม่ได้)

แนวคิด: DP แบบ State Machine

State Definition (6 States)

แบ่งตาม จำนวน A (0 หรือ 1) และ ท้าย L ติดกัน (0, 1, 2):

จริงๆ รวม LL เข้า L, ALL เข้า AL ได้ เพราะ Transition เหมือนกัน

Recurrence (i ≥ 3)

// 0 A states
p[i]  = p[i-1] + a[i-1] + l[i-1]           // เพิ่ม P
l[i]  = p[i-1] + p[i-2] + a[i-1] + a[i-2]  // เพิ่ม L (จาก state ที่ท้ายไม่ใช่ L)

// 1 A states
a[i]  = al[i-1] + ap[i-1]                  // เพิ่ม A (จาก 0 A states)
al[i] = ap[i-1] + ap[i-2]                  // เพิ่ม L (จาก 1 A, ท้ายไม่ใช่ L)
ap[i] = ap[i-1] + al[i-1]                  // เพิ่ม P (จาก 1 A states)

Base Cases

i=0: p=1, a=1, l=1, ap=1, al=1  (empty string)
i=1: p=1, a=1, l=1, ap=1, al=1  (P, A, L)
i=2: p=3, a=2, l=3, ap=2, al=2  (PP,PA,AP | AA,AL,LA | LL,LP,PL | AP,AL | AL,LA)

โค้ด C++

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

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

ตารางค่า n=1..5

ความซับซ้อน

• Time: O(n)
• Space: O(n) (ลดเป็น O(1) ได้)

Input / Output

Input:  3
Output: 19