rewardable.py

'''
dp[i][0] stands for # of string whose length is i ends with O
dp[i][1] stands for # of string whose length is i ends with A
dp[i][2] stands for # of string whose length is i ends with L
'''

def numOfRewardable(self, n):
        dp = [[0, 0, 0] for i in range(max(4, n + 1))]
        dp[1] = [1, 1, 1]
        dp[2] = [3, 2, 3]
        dp[3] = [7, 4, 8]

        for i in range(4, n + 1):
            dp[i][2] = sum(dp[i - 1])
            # ends up with O
            dp[i][1] = dp[i - 1][1] + dp[i - 2][1] + dp[i - 3][1]
            # ends up with A
            # replace M[i-1][1]'s last A with O
            # replace M[i-2][1]'s last A with O and insert L after that
            # replace M[i-3][1]'s last A with O and insert LL after that
            dp[i][0] = dp[i][2] - (dp[i - 3][1] + dp[i - 3][2])
            # ends up with L
            # ___ALL + L and ___OLL + L cases that cause invalid string have been counted
            # in M[i][2] (i.e sum(M[i-1]))
            # then drop them by reducing M[i-3][1] + M[i-3][2]
            # note that LLL + L won't be counted in M[i][2] because of LLL is already illegal
        return sum(dp[n])