class Solution {
public:
int checkRecord(int n) {
//a0[0]=1, a1[0]=0;
//a0[1]=2, a1[1]=1;
//a0[2]=4, a1[2]=4;
//a0[i]= a0[i1] // +p
// + a0[i2] //+PL
// + a0[i3] //+PLL,
//a1[i]= a0[i1]  +A
// + a1[i1]  +P
// + a1[i2]  +PL
// + a1[i3]  +PLL
// + a0[i2]  +AL
// + a0[i3]  +ALL
vector<long> A0(n+1, 1), A1(n+1,0);
A0[1]=2; A1[1]=1;
A0[2]=4; A1[2]=4;
for (int i=3; i<=n; i++) {
A0[i]=(A0[i1] + A0[i2] + A0[i3]) % (long)1000000007;
A1[i]= (A0[i1] + A1[i1] + A1[i2] + A1[i3] + A0[i2] + A0[i3]) % (long)1000000007;
}
return (A0.back() + A1.back())% (long)1000000007;
}
};
C++ 10 lines, O(n) DP, 29ms, comments inline


@sgsg You should point out that you are using undocumented behavior of the C++ vectors for the base cases. That's why you are able to use vector::back() even for the base cases.