LeetCode Student Attendance Record II Given a positive integer n, return the number of all possible attendance records with length n, which will be regarded as rewardable. The answer may be very large, return it after mod 10⁹ + 7. A student attendance record is a string that only contains the following three characters:

1. ‘A’ : Absent.
2. ‘L’ : Late.
3. ‘P’ : Present.

A record is regarded as rewardable if it doesn’t contain more than one ‘A’ (absent) or more than two continuous ‘L’ (late). Example 1:

Input: n = 2
Output: 8
Explanation:
There are 8 records with length 2 will be regarded as rewardable:
"PP" , "AP", "PA", "LP", "PL", "AL", "LA", "LL"
Only "AA" won't be regarded as rewardable owing to more than one absent times.

Note: The value of n won’t exceed 100,000.

---

在上一题的基础上增大了难度，这一题给定数组n，问长度为n的学生出席字符串，有多少种可能让该学生获奖。 显然是DP问题，不过是三维DP。令dp[n][i][j]表示长度为n的字符串，包含i个’A’并且以j个’L’结尾的字符串个数。那么有如下的递推公式： dp[n][0][0]=sum(dp[n-1][0])：要求长度为n、包含0个’A’，且以0个’L’结尾的字符串个数；所以前n-1肯定也只包含0个’A’，但是前n-1可以以0、1或2个’L’结尾，因为我第n个字符不放’L’就能保证前n以0个’L’结尾。所以dp[n][0][0]=sum(dp[n-1][0])。其他的类似分析有：

• dp[n][0][1]=dp[n-1][0][0]
• dp[n][0][2]=dp[n-1][0][1]
• dp[n][1][0]=sum(dp[n-1][0])+sum(dp[n-1][1])
• dp[n][1][1]=dp[n-1][1][0]
• dp[n][1][2]=dp[n-1][1][1]

代码如下： [cpp] const int kMOD = 1000000007; class Solution { private: long long getSum(vector<int>& v) { long long ans = 0; for(const int &i : v) ans += i; return ans % kMOD; } public: int checkRecord(int n) { vector<vector<int>> dp = {{1, 1, 0}, {1, 0, 0}}; for(int i = 2; i <= n; ++i){ vector<vector<int>> ndp = {{0, 0, 0}, {0, 0, 0}}; ndp[0][0] = getSum(dp[0]); ndp[0][1] = dp[0][0]; ndp[0][2] = dp[0][1]; ndp[1][0] = (getSum(dp[1]) + getSum(dp[0])) % kMOD; ndp[1][1] = dp[1][0]; ndp[1][2] = dp[1][1]; dp = ndp; } return (getSum(dp[0]) + getSum(dp[1])) % kMOD; } }; [/cpp] 本代码提交AC，用时612MS。]]>