# Go, Simple DP, Copious Comments

• Thanks @sgsg for the basis for this solution.

``````func checkRecord(n int) int {
mod := int(1e9) + 7
dp := [][]int{
[]int{1, 2, 4}, //dp[0][i] == sequences of length i, having zero A's
[]int{0, 1, 4}, //dp[1][i] == sequences of length i, having one A
}

for i := 3; i <= n; i++ {
// Case 1: No A's, Adding only P's and L's
dp[0] = append(dp[0], 0)
dp[0][i] += dp[0][i-1] // Case 1.1: End in P
dp[0][i] += dp[0][i-2] // Case 1.2: End in L, previous P ([i-2]+PL)
dp[0][i] += dp[0][i-3] // Case 1.3: End in L, previous PL ([i-3]+PLL)
// Why no +L, +LL, +LLP? These are already covered by +PL, +PLL, (+PLL, +P)
dp[0][i] %= mod

// Case 2: One A
dp[1] = append(dp[1], 0)
// Case 2.1 Have no A's, adding one A
dp[1][i] += dp[0][i-1] // Case 2.1.1 End in A, need dp[0][i-1]
dp[1][i] += dp[0][i-2] // Case 2.1.2 End in L, previous A ([i-1]+AL)
dp[1][i] += dp[0][i-3] // Case 2.1.3 End in L, previous AL ([i-2]+ALL)
// why don't we need +ALP, and +APL?
// These were covered in prior iterations as [i-3]+AL, and [i-2]+A respectively;
// [i-1]+P and [i-2]+PL cover these cases in this iteration
// Case 2.2 Already have an A, Adding P's and L's only
dp[1][i] += dp[1][i-1] // Case 2.2.1 End in P, need dp[1][i-1]
dp[1][i] += dp[1][i-2] // Case 2.2.2 End in L, previous P ([i-2]+PL)
dp[1][i] += dp[1][i-3] // Case 2.2.3 End in L, previous PL ([i-3]+PLL)
dp[1][i] %= mod
}
return (dp[0][n] + dp[1][n]) % mod // Now we just add the final No-A's + Have-A cases
}
``````

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