Python, Straightforward DP with Explanation


  • 3

    At time t where every report is length t, Let a, b, c be sequence types without an 'A' ending in N, NL, LL; and d,e,f be sequence types with an 'A' ending in N, NL, LL. (Here, N will denote a non-'L' character.) These types are disjoint, and exhaustive (their union is the set of all valid reports.) At the beginning when t = 1, a = b = d = 1 and we should compute N-1 more steps.

    From a sequence of type a, b, c, we can write an 'A' to give us a sequence of type d, or a 'P' to give us a sequence of type a. From a sequence of type d, e, f, we can write a 'P' to give us a sequence of type d. From a sequence of type a, b, d, e, we can write an 'L' to give a sequence of (respectively) b, c, e, f. These are all the letters we could write in any situation. Working backwards, we can get the sums for a,b,c,d,e,f written below.

    def checkRecord(self, N):
        MOD = 10**9 + 7
        a = b = d = 1
        c = e = f = 0
        for _ in xrange(N-1):
            a, b, c, d, e, f = (a+b+c)%MOD, a, b, (a+b+c+d+e+f)%MOD, d, e
        
        return (a+b+c+d+e+f)%MOD
    

  • 0
    B

    @awice Very nice solution, it's interesting that N could be None.


Log in to reply
 

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