552. 学生出勤记录 II 超简单的理解思路 击败88.57

大类只有2种情况 (1)无A :dp[n]种 . (2)有1个A: d[j-1]*dP[n-j]，注意j=1,2,3,…,n。
此时无A的情况，只用考虑P和L的的排列。初始化dP[0]=1, dP[1]=2,dP[2]=4，n<=2时候显而易见，因为L的情况不用管！！！

现在难点是：如何排除3个L的情况!!!

以n=4为例子 :那么对于第1个元素，可以是P可以是L，如果是P就好办了（直接dp[3]），如果是L呢？

• P[]: dp[3]
• LP[] :第1个是L，第2个可以是P，那么也好办，直接dp[2],因为后面就2个元素
• LLP[] ：第2个如果是L呢？也好办，第3个一定是P，直接dp[1]。

好了，已经发现规律了，dp[n]=dp[n-1]+dp[n-2]+dp[n-3];
最后（1）和（2）加起来就是答案了。

class Solution {
    public int checkRecord(int n) {
        if(n==1)return 3;
        long []dp = new long[n+1];
        dp[0] = 1;
        dp[1] = 2;
        dp[2] = 4;
        long MOD = 1000000007;
        for(int i=3;i<=n;i++){
            dp[i] = ((dp[i-1] + dp[i-2])%MOD +dp[i-3])%MOD;
        }  
        long res = 0;

        //有1个A
        for(int i=1;i<=n;i++){
            long tmp = (dp[i-1]*dp[n-i])%MOD;
            res = (res+tmp)%MOD;
        }
        res = (res+dp[n])%MOD;
        return (int)res;
    }
}