本文共 1747 字，大约阅读时间需要 5 分钟。

552. Student Attendance Record II

博主看到这题时候第一感觉就是DP方法，但是想了一会方程式写不出来，然后开始怀疑是不是动态方程，想了一下过程感觉极其复杂。看了讨论区，茅塞顿开。首先讲解一下过程。首先我们定义一个问题，我们在字符串最后添加一个字符只能是以A L P三种结尾，因此定义T（n）是长度为n的所有情况。那么：

T（n） = A（n） + L（n） + P（n）代表最终是以A L P 结尾的三种情况累加。

那么我们逐个分析：

P(n）代表什么意思呢：是长度为n且以P为结尾。那么 P（n）是不是可以表示成长度为n-1 分别以A L P 结尾最后添加一个P形成n长度。

P（n） = P（n - 1） + A（n - 1）+ L（n - 1）

这个非常好理解吧。

我们来考虑L（n）情况：

同样以L结尾长度为n的情况可以分解一下，分别以长度n-1，A L P结尾的字符串最后添加一个L就形成了n长度的L（n），但是这里有一种情况不可以，也就是长度为n-1以L结尾的字符需要特殊考虑。比如AL+L可以，但是LL + L不可以。也就是我们需要考虑n-2到底是不是L。

L（n） = A（n - 1）+ P（n - 1）+（A（n - 2） + P（n - 2））

我这么写不知道大家能不能理解，也就是说将L（n - 1）当中的L（n - 2）删除，本来L（n - 1）是包含 A（n - 2）+ L (n - 2) + P (n - 2)三种，但是第二种不符合。应该明白了吧。

先来来考虑A（n），也是比较复杂的情况：

A（n）考虑长度n-1的三种情况，我们知道如果里面已经有了A那么必然不存在。我们定义 NoAL(n) 和 NoAP(n) 代表什么意思呢，就是说NoAL(n)表示长度为n以L结尾的字符串，同时不包含A。同理NoAP(n)代表长度为n以P结尾的字符串，同时不包含A。那么：

NoAL(n) = NoAP(n-1) + NoAP(n-2)

NoAP(n) = NoAL(n-1) + NoAP(n-1)

大家理解上面L（n）应该很清楚能明白上面两个式子。

那么： A(n) = NoAL(n-1) + NoAP(n-1) 我们观察和代入可以得到下面的公式： NoAL(n-1) = NoAP(n-2) + NoAP(n-3) NoAP(n-1) = NoAL(n-2) + NoAP(n-2)

A(n) = A(n-1) + A(n-2) + A(n-3)

至此关系式子已经完成，需要填写一下边界，那么我们上代码：

class Solution {
   public:	int checkRecord(int n) {
   		if (n == 1)			return 3;		if (n == 2)			return 8;		vector
   
     A(n + 1, 0);		vector
    
      L(n + 1, 0);		vector
     
       P(n + 1, 0);		A[1] = 1;L[1] = 1;P[1] = 1;		A[2] = 2;A[3] = 4;		L[2] = 3;P[2] = 3;		for (int i = 3; i <= n; i++)		{
   			P[i] = ((A[i - 1] + L[i - 1]) % mod + P[i - 1]) % mod;			L[i] = ((A[i - 1] + P[i - 1]) % mod + (A[i - 2] + P[i - 2]) % mod) % mod;			if (i > 3)				A[i] = ((A[i - 1] + A[i - 2]) % mod + A[i - 3]) % mod;		}		return (((A[n] % mod + L[n] % mod) % mod + P[n] % mod) % mod);	}private:	static const int mod = 1000000007;};
     
    
   

这是一个非常nice的题目，看到这个解题过程非常舒服。

转载地址：http://ogfnb.baihongyu.com/