Go, Simple DP, Copious Comments


  • 0
    A

    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
    }
    

Log in to reply
 

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