[LeetCode] 552. Student Attendance Record II #552

grandyang · 2019-05-30T16:22:58Z

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:

'A' : Absent.
'L' : Late.
'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 同步地址：

#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 题目讲解汇总(持续更新中...)

The text was updated successfully, but these errors were encountered: