C++ में स्टूडेंट अटेंडेंस रिकॉर्ड II समस्या

मान लीजिए हमारे पास एक पॉजिटिव इंटीजर n है, हमें लंबाई n के सभी संभावित अटेंडेंस रिकॉर्ड्स की संख्या ढूंढनी है जो रिवॉर्डेबल हों। चूंकि उत्तर बहुत बड़ा हो सकता है, हम इसे मॉड 10⁹ + 7 का उपयोग करके लौटाएंगे।

स्टूडेंट अटेंडेंस रिकॉर्ड में स्ट्रिंग में केवल ये तीन वर्ण हो सकते हैं:

'A' का अर्थ है अनुपस्थित (Absent)।
'L' का अर्थ है देर से आना (Late)।
'P' का अर्थ है उपस्थित (Present)।

एक अटेंडेंस को रिवॉर्डेबल माना जाता है यदि इसमें एक से अधिक 'A' नहीं हैं या लगातार दो से अधिक 'L' नहीं हैं।

यदि इनपुट 2 है, तो आउटपुट 8 होगा, क्योंकि हम 8 संभावित तरीके उत्पन्न कर सकते हैं जो रिवॉर्डेबल हैं: [PP, AP, PA, LP, PL, AL, LA, LL], केवल AA नहीं होगा।

समाधान दृष्टिकोण (डायनामिक प्रोग्रामिंग)

add() फंक्शन परिभाषित करें जो a, b लेता है और ((a % m) + (b % m)) % m लौटाता है।
मुख्य मेथड से:
- आकार n+1 के ऐरे p, a, l, ap, al परिभाषित करें।
- यदि n == 1, तो 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
- i = 3 से n तक लूप करें:
  - 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])
- add(add(p[n], l[n]), a[n]) लौटाएं।

C++ कार्यान्वयन

#include <bits/stdc++.h>
using namespace std;

typedef long long int lli;
const lli MOD = 1e9 + 7;

class Solution {
public:
    lli add(lli a, lli b) {
        return ((a % MOD) + (b % MOD)) % MOD;
    }
    
    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);
    return 0;
}