My O(n) solution get TLE...


  • 0

    Strange....

    class Solution(object):
        def checkRecord(self, n):
            dp = [[0, 0, 0] for i in range(n)]
            dp[0] = [1, 1, 0]
            for i in range(n):
                if i == 0: 
                    continue
                dp[i][0] = sum(dp[i - 1]) % 1000000007
                dp[i][1] = dp[i - 1][0] 
                dp[i][2] = dp[i - 1][1]
                
            res = [1]
            res.extend([sum(x) % 1000000007 for x in dp])
            count = res[n]
            for i in range(n):
                front = i - 0
                back = n - i - 1
                count += res[front] * res[back]
                count = count % 1000000007
            
            return count
    

Log in to reply
 

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