# C++ 10 lines, O(n) DP, 29ms, comments inline

• ``````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[i-1] // +p
//       + a0[i-2] //+PL
//       + a0[i-3] //+PLL,
//a1[i]= a0[i-1]  -- +A
//       + a1[i-1] -- +P
//       + a1[i-2] -- +PL
//       + a1[i-3] -- +PLL
//       + a0[i-2] -- +AL
//       + a0[i-3] -- +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[i-1] + A0[i-2] + A0[i-3]) % (long)1000000007;
A1[i]= (A0[i-1] + A1[i-1] + A1[i-2] + A1[i-3] + A0[i-2] + A0[i-3]) % (long)1000000007;
}
return (A0.back() + A1.back())% (long)1000000007;
}
};
``````

• A0[i] is the number of sequences with length i that does not have 'A'.
A1[i] is the number of sequences with length i that has only one 'A'.

• @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.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.