552. Student Attendance Record II
虽然知道这是一道DP题,但是这个dp状态真的很难找。。。
dp[i] = dp[i].[end with 'P'] + dp[i].[end with 'PL'] + dp[i].[end with 'PLL'] + dp[i].[end with 'LLL']
class Solution(object):
def checkRecord(self, n):
if n == 1:
return 3
if n == 0:
return 0
nums = [1, 1, 2]
i = 2
while i < n:
nums.append((nums[i] + nums[i-1] + nums[i-2])% 1000000007)
i += 1
result = (nums[n] + nums[n-1] + nums[n-2]) % 1000000007
# 这一行表示把A插入到什么位置且A前的一段和A后的一段的变化情况
for i in range(n):
result += nums[i+1] * nums[n-i] % 1000000007
result %= 1000000007
return result