# Java 4 lines DP solution with state transition table explained

• 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;
}
``````

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