# C++ Solution, O(n) Time, O(1) Space, Simple DP

• A(absence), L(last continuous late )
A-1, L-0 -> L0
A-1, L-1 -> L1
A-1, L-2 -> L2
A-0, L-0 -> l0
A-0, L-1 -> l1
A-0, L-2 -> l2

dp[i] -> dp[i + 1]
Just use A/L/P to test each state.
You can find the state transfer formulation in the following code.

`class Int` used to handle int overflow.

``````class Solution {

int NUM = 1000000007;
class Int {
public:
Int(int val) : val_(val) {}
operator int() {return val_;}
Int operator+(const Int& lhs) {
return Int((val_ + lhs.val_) % 1000000007);
}
int val_;
};

public:
int checkRecord(int n) {
IntL0 = 1, L1 = 0, L2 = 0,  l0 = 1, l1 = 1, l2 = 0;
for (int i = 1; i < n; i++) {
Int L0_ = L0 + L1 + L2 + l0 + l1 + l2;
Int L1_ = L0;
Int L2_ = L1;
Int l0_ = l0 + l1 + l2;
Int l1_ = l0;
Int l2_ = l1;

L0 = L0_, L1 = L1_, L2 = L2_, l0 = l0_, l1 = l1_, l2 = l2_;
}
return L0 + L1 + L2 + l0 + l1 + l2;
}
};
``````

This version is a little bit faster...... UM..

``````int checkRecord(int n) {
int l0 = 1, l1 = 1, l2 = 0, L0 = 1, L1 = 0, L2 = 0;
for (int i = 1; i < n; i++) {
int L0_ = (((L0 + L1) % NUM + L2) % NUM + ((l0 + l1) % NUM + l2) % NUM) % NUM;
int L1_ = L0;
int L2_ = L1;
int l0_ = ((l0 + l1) % NUM + l2) % NUM;
int l1_ = l0;
int l2_ = l1;

L0 = L0_, L1 = L1_, L2 = L2_, l0 = l0_, l1 = l1_, l2 = l2_;
}
//cout << L0 << endl << L1 << endl << L2 << endl << l0 << endl << l1 << endl << l2 << endl;
return (((L0 + L1) % NUM + L2) % NUM + ((l0 + l1) % NUM + l2) % NUM) % NUM;
}
``````

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