Elegant Python DP Solution, O(n) time, O(1) space


  • 0
    class Solution(object):
        def checkRecord(self, n):
            """
            :type n: int
            :rtype: int
            """
            L = pow(10, 9) + 7
            dp = [1, 0, 0, 0, 0, 0] 
                  # 0 A 0 L, 0 A 1 L, 0 A 2 L, 1 A 0 L,  1 A 1 L, 1 A 2 L
            for i in xrange(n):
                dp = [sum(dp[:3]) % L, dp[0], dp[1], sum(dp) % L, dp[3], dp[4]]
            return sum(dp) % L
    

Log in to reply
 

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