4-liner Python DP with brief explanation

  • 0

    Let noA[i+1] be the number of rewardable no 'A' records with length i, then a rewardable no 'A' record could only end with 'P', 'PL' or 'PLL'. So we have

    noA[i+1] = noA[i] + noA[i-1] + noA[i-2].

    Padding a rewardable no 'A' record with proper length to left and right of an 'A' will give a rewardable with 'A' record.

        def checkRecord(self, n):
            if n < 3: return 1 if n == 0 else (3 if n == 1 else 8)
            noA = [1, 1, 2]
            while (len(noA) < n+3): noA.append(sum(noA[-3:])%1000000007)            
            return (sum((noA[i+1]*noA[n-i]) for i in range(n+1)))%1000000007

Log in to reply

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