[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)，代码如下:

	class Solution {
	public:
	int checkRecord(int n) {
	const int MOD = 1000000007;
	//dp[i][j][k], represent # of all possibe attendance record with length i,
	//j As and ends with k Ls, where 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]
	vector<vector<vector<int>>> dp(2, vector<vector<int>>(2, vector<int>(3, 0)));
	//init
	dp[0][0][0] = 1;
	dp[0][0][1] = 1;
	dp[0][0][2] = 0;
	dp[0][1][0] = 1;
	dp[0][1][1] = 0;
	dp[0][1][2] = 0;
	//dp, rolling array
	int e = 1;
	for(int i = 2; i <= n; ++i, e ^= 1)
	{
	dp[e][0][0] = ((dp[e ^ 1][0][0] + dp[e ^ 1][0][1]) % MOD + dp[e ^ 1][0][2]) % MOD;
	dp[e][0][1] = dp[e ^ 1][0][0];
	dp[e][0][2] = dp[e ^ 1][0][1];
	dp[e][1][0] = ((dp[e ^ 1][1][0] + dp[e ^ 1][1][1]) % MOD + dp[e ^ 1][1][2]) % MOD;
	dp[e][1][0] += dp[e][0][0];
	dp[e][1][0] %= MOD;
	dp[e][1][1] = dp[e ^ 1][1][0];
	dp[e][1][2] = dp[e ^ 1][1][1];
	}
	//count
	int res = 0;
	for(int j = 0; j <= 1; ++j)
	{
	for(int k = 0; k <= 2; ++k)
	{
	res += dp[e ^ 1][j][k];
	res %= MOD;
	}
	}
	return res;
	}
	};

view raw Student Attendance Record II.cpp hosted with ❤ by GitHub