Let `AnLn`

denote number of strings containing n `A`

's and ending with n `L`

's

For example:

When `n = 1`

we have:

```
A0L0: P
A0L1: L
A0L2:
A1L0: A
A1L1:
A1L2:
Done:
```

When `n = 2`

we have:

```
A0L0: LP, PP
A0L1: PL
A0L2: LL
A1L0: AP, LA, PA
A1L1: AL
A1L2:
Done: AA
```

In general we have this transition table:

```
-----+---------------
INIT | A -- L -- P --
-----+---------------
A0L0 | A1L0 A0L1 A0L0
A0L1 | A1L0 A0L2 A0L0
A0L2 | A1L0 Done A0L0
A1L0 | Done A1L1 A1L0
A1L1 | Done A1L2 A1L0
A1L2 | Done Done A1L0
```

From the transition table we see that:

`A0L0`

of `n`

can result from `A0L0 + A0L1 + A0L2`

of `n - 1`

by appending `P`

`A0L1`

of `n`

can only result from `A0L0`

of `n - 1`

by appending `L`

and so on...

That's why in each iteration we update:

`dp[0] = dp[0] + dp[1] + dp[2]`

`dp[1] = dp[0]`

and so on...

```
public int checkRecord(int n) {
int[] dp = { 1, 1, 0, 1, 0, 0 }; // init table for n = 1
for (int i = 2; i <= n; i++) // updating table for n = i
dp = new int[] { sum(dp, 0, 2), dp[0], dp[1], sum(dp, 0, 5), dp[3], dp[4] };
return sum(dp, 0, 5);
}
static int sum(int[] arr, int l, int h) {
int s = 0;
for (int i = l; i <= h; i++)
s = (s + arr[i]) % 1000000007;
return s;
}
```