[LeetCode]Student Attendance Record II

这道题最开始的想法是参考POJ的这道题，建自动机然后矩阵快速幂，因为题目有点相似。但后来仔细想了一下还是不好做，因为我们不允许的substring是LLL, LLLL...，数量太多，所以我们还是退而求其次用dp来接这道题。我们用dp[i][j][k]表示长度为i，有j个A并且结尾有k个L的情况下，distinct string的数量。显然j, k 满足条件 0 <= j <= 1 && 0 <= k <= 2。我们有递推公式：

• dp[i][0][0] = dp[i - 1][0][0] + dp[i - 1][0][1] + dp[i - 1][0][2] 
• dp[i][0][1] = dp[i - 1][0][0] 
• dp[i][0][2] = dp[i - 1][0][1] 
• dp[i][1][0] = dp[i - 1][1][0] + dp[i - 1][1][1] + dp[i - 1][1][2] + dp[i - 1][0][0] + dp[i - 1][0][1] + dp[i - 1][0][2] 
• dp[i][1][1] = dp[i - 1][1][0] 
• dp[i][1][2] = dp[i - 1][1][1]

按照递推公式计算即可，最后统计所有长度为i满足条件的数量，用rolling array可以优化成常数空间，时间复杂度O(n)，代码如下: