552. 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 109 + 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.

 

这道题是之前那道 Student Attendance Record I 的拓展,但是比那道题难度要大的多。从题目中说结果要对一个很大的数取余,说明结果是一个很大很大的数。一般来说这种情况不能用递归来求解,可能会爆栈,所以要考虑利用数学方法或者动态规划 Dynamic Programming 来做。其实博主最先看到这题的时候,心想这不就是高中时候学的排列组合的题吗,于是又在想怎么写那些A几几,C几几的式子来求结果,可惜并没有做出来。现在想想怎么当初高中的自己这么生猛,感觉啥都会的样子,上知天文下知地理,数理化生样样精通的感觉,燃鹅随着时间的推移,所有的一切都还给了老师。总感觉这题用数学的方法应该也可以解,但是看网上的大神们都是用 DP 做的,没办法,那只能用 DP 来做了。下面这种做法来自 大神 lixx2100 的帖子,这里定义一个三维的 dp 数组,其中 dp[i][j][k] 表示数组前i个数字中,最多有j个A,最多有k个连续L的组合方式,那么最终要求的结果就保存在dp[n][1][2]中。然后来考虑如何求 dp[i][j][k] 的状态转移方程,首先来取出前一个状态下的值,就是前 i-1 个数的值 dp[i-1][j][2],即数组前 i-1 个数中,最多有j个A,最多有2个连续L的排列方式,然后如果 j>0,那么再加上 dp[i-1][j-1][2],即加上了最多有j-1个A的情况,并对超大数取余;如果 k>0,则再加上 dp[i-1][j][k-1],即加上了最多有j个A,最多有 k-1 个连续L的排列方式,其实博主并没有完全理解为什么要这么更新,如果有大神们理解了这么做的含义,请不吝赐教,在下方留言告知博主啊~

 

解法一:

class Solution {
public:
    int checkRecord(int n) {
        int M = 1e9 + 7;
        int dp[n + 1][2][3] = {0};
        for (int j = 0; j < 2; ++j) {
            for (int k = 0; k < 3; ++k) {
                dp[0][j][k] = 1;
            }
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j < 2; ++j) {
                for (int k = 0; k < 3; ++k) {
                    int val = dp[i - 1][j][2];
                    if (j > 0) val = (val + dp[i - 1][j - 1][2]) % M;
                    if (k > 0) val = (val + dp[i - 1][j][k - 1]) % M;
                    dp[i][j][k] = val;
                }
            }
        }
        return dp[n][1][2];
    }
};

 

下面这种方法来自 大神 KJer 的帖子,大神帖子里面的讲解写的很详细,很赞,也不难读懂。定义了三个 DP 数组 P, L, A,其中 P[i] 表示数组 [0,i] 范围内以P结尾的所有排列方式,L[i] 表示数组 [0,i] 范围内以L结尾的所有排列方式,A[i] 表示数组 [0,i] 范围内以A结尾的所有排列方式。那么最终所求的就是 P[n-1] + L[n-1] + A[n-1] 了,难点就是分别求出 P, L, A 数组的递推公式了。

首先来看P数组的,P字符没有任何限制条件,可以跟在任何一个字符后面,所以有 P[i] = A[i-1] + P[i-1] + L[i-1]

再来看L数组的,L字符唯一的限制条件是不能有超过两个连续的L,那么在P和L字符后面可以加1一个L,如果前一个字符是L,要看再前面的一位是什么字符,如果是P或着A的话,可以加L,如果是L的话,就不能再加了,否则就连续3个了,所以有 L[i] = A[i-1] + P[i-1] + A[i-2] + P[i-2]

最后来看A数组的,这个比较麻烦,字符A的限制条件是整个字符串最多只能有1个A,那么当前一个字符是A的话,就不能再加A来,当前一个字符是P或者L的话,要确定之前从没有A出现过,才能加上A。那么实际上还需要定义两个数组 P1, L1, 其中 P1[i] 表示数组 [0,i] 范围内以P结尾的不包含A的所有排列方式,L1[i] 表示数组 [0,i] 范围内以L结尾的不包含A的所有排列方式,根据前两种情况不难推出 P1 和 L1 的递推公式,再加上A的递推公式如下:

A[i] = P1[i-1] + L1[i-1]

P1[i] = P1[i-1] + L1[i-1]

L1[i] = P1[i-1] + P1[i-2]

将第二第三个等式多次带入第一个等式,就可以将 P1 和 L1 消掉,可以化简为:

A[i] = A[i-1] + A[i-2] + A[i-3]

这样就可以少定义两个数组了,状态转移方程有了,代码也就不难写了:

 

解法二:

class Solution {
public:
    int checkRecord(int n) {
        int M = 1e9 + 7;
        vector<int> P(n), L(n), A(n);
        P[0] = 1; L[0] = 1; A[0] = 1;
        if (n > 1) { L[1] = 3; A[1] = 2; }
        if (n > 2) A[2] = 4;
        for (int i = 1; i < n; ++i) {
            P[i] = ((P[i - 1] + L[i - 1]) % M + A[i - 1]) % M;
            if (i > 1) L[i] = ((A[i - 1] + P[i - 1]) % M + (A[i - 2] + P[i - 2]) % M) % M;
            if (i > 2) A[i] = ((A[i - 1] + A[i - 2]) % M + A[i - 3]) % M;
        }
        return ((A[n - 1] + P[n - 1]) % M + L[n - 1]) % M;
    }
};

 

下面这种方法来自 大神 dettier 的帖子,这里面定义了两个数组P和 PorL,其中 P[i] 表示数组前i个数字中1以P结尾的排列个数,PorL[i] 表示数组前i个数字中已P或者L结尾的排列个数。这个解法的精髓是先不考虑字符A的情况,而是先把定义的这个数组先求出来,由于P字符可以再任意字符后面加上,所以 P[i] = PorL[i-1];而 PorL[i] 由两部分组成,P[i] + L[i],其中 P[i] 已经更新了,L[i] 只能当前一个字符是P,或者前一个字符是L且再前一个字符是P的时候加上,即为 P[i-1] + P[i-2],所以 PorL[i] = P[i] + P[i-1] + P[i-2]。

那么这里就已经把不包含A的情况求出来了,存在了 PorL[n] 中,下面就是要求包含一个A的情况,那么就得去除一个字符,从而给A留出位置。就相当于在数组的任意一个位置上加上A,数组就被分成左右两个部分了,而这两个部分当然就不能再有A了,实际上所有不包含A的情况都已经在数组 PorL 中计算过了,而分成的子数组的长度又不会大于原数组的长度,所以直接在 PorL 中取值就行了,两个子数组的排列个数相乘,然后再把所有分割的情况累加起来就是最终结果啦,参见代码如下:

 

解法三:

class Solution {
public:
    int checkRecord(int n) {
        int M = 1e9 + 7;
        vector<long> P(n + 1), PorL(n + 1);
        P[0] = 1; PorL[0] = 1; PorL[1] = 2;
        for (int i = 1; i <= n; ++i) {
            P[i] = PorL[i - 1];
            if (i > 1) PorL[i] = (P[i] + P[i - 1] + P[i - 2]) % M;
        }
        long res = PorL[n];
        for (int i = 0; i < n; ++i) {
            long t = (PorL[i] * PorL[n - 1 - i]) % M;
            res = (res + t) % M;
        }
        return res;
    }
};

 

Github 同步地址:

https://github.com/grandyang/leetcode/issues/552

 

类似题目:

Student Attendance Record I

 

参考资料:

https://leetcode.com/problems/student-attendance-record-ii/

https://leetcode.com/problems/student-attendance-record-ii/discuss/101638/Simple-Java-O(n)-solution

https://leetcode.com/problems/student-attendance-record-ii/discuss/101633/Improving-the-runtime-from-O(n)-to-O(log-n)

https://leetcode.com/problems/student-attendance-record-ii/discuss/101643/Share-my-O(n)-C%2B%2B-DP-solution-with-thinking-process-and-explanation

 

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation