552 学生出勤记录 II（递推-动态规划-枚举技巧）

红太狼 2022-08-31 05:56 148阅读 0赞

**1. 问题描述：**

给定一个正整数 n，返回长度为 n 的所有可被视为可奖励的出勤记录的数量。 答案可能非常大，你只需返回结果mod 10 ^ 9 + 7的值。学生出勤记录是只包含以下三个字符的字符串：  
'A' : Absent，缺勤  
'L' : Late，迟到  
'P' : Present，到场  
如果记录不包含多于一个'A'（缺勤）或超过两个连续的'L'（迟到），则该记录被视为可奖励的。

**示例 1:**

输入: n = 2  
输出: 8  
解释：  
有8个长度为2的记录将被视为可奖励：  
"PP" , "AP", "PA", "LP", "PL", "AL", "LA", "LL"  
只有"AA"不会被视为可奖励，因为缺勤次数超过一次。  
注意：n 的值不会超过100000。  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/student-attendance-record-ii

**2. 思路分析：**

分析题目可以知道我们可以在短的字符串后面尝试添加字母A，L，P，判断是否可以构成更长的满足要求的字符串...直到最终构成长度为n的字符串，将所有长度为n的合法方案累加起来就是答案。这个过程其实是一个**递推**的过程，由上一个状态递推到当前的状态，一直到目标状态，所以我们可以使用动态规划递推的思路解决（想到递推的思路很重要）。使用dp解决首先需要考虑状态表示，也即需要使用到哪些值（方便后面的状态转移），可以发现我们需要用到的有当前的字符个数，当前字母A的数目，当前连续字母L的数目，所以我们可以定义三维的数组或者列表，因为使用的是python语言所以可以定义为三维的列表，其中dp\[i\]\[j\]\[k\]表示当前字符个数为i，字母A的个数为j，连续字母L的数目为k的所有方案，对于这种常规的递推的状态转移，有**两种常见的dp转移**的方法，也即对应的状态计算，第一种是由上一个可能的状态集合转移到当前的状态，也即计算由上一个状态转移到当前状态的方案数目，可以发现dp\[i\]\[j\]\[k\]由上一个状态集合转移到当前的状态的时候需要判断很多的情况所以比较难写。第二种方法是我们可以考虑枚举下一个状态，也即枚举下一个位置可能填什么才能够从当前的状态转移到下一个可能的状态，这种枚举方式会更好处理，我们只需要判断下一个位置填字母A，L，P是否合法，也即是否可以由当前的状态转移到下一个状态。使用三层循环枚举即可，第一层循环当前字符的个数，第二层循环表示字母A的个数，第三层循环表示连续字母L的个数，在循环中判断当前状态的下一个位置填字母A，L对应的j，k的变量是否合法，在转移到下一个状态的时候需要累加上当前状态的方案数目即可。最后遍历一下字符个数为n的字母A和字母L合法的状态数目，累加起来就是答案，我们可以采用第二种枚举下一个位置可能填的字母情况的枚举方法这样会更容易处理。主要是题目中蕴含的递推的思想。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70][]

**3. 代码如下：**

**发现python代码与java代码差别太大了，python差不多8s，java只需要230ms左右。**

**python代码（8s）**

class Solution:
        def checkRecord(self, n: int) -> int:
            # 声明一个(n + 1) * 2 * 3的三维列表, dp[i][j][k]表示i个字符, j个字母A, k个连续的字母L 
            dp = [[[0] * 3 for i in range(2)] for j in range(n + 1)]
            # 初始状态表示当前有0个字母, 0个A, 0个连续的字母L的方案数目为1
            dp[0][0][0] = 1
            mod = 10 ** 9 + 7
            for i in range(n):
                # 第二层表示字母A的数目
                for j in range(2):
                    # 第三层表示连续字母L的数目
                    for k in range(3):
                        # 枚举的是下一个位置, 因为求解的是方案数目, 所以需要累加上当前状态的dp值
                        # 判断下一个位置填字母A的情况
                        if j == 0: dp[i + 1][j + 1][0] = (dp[i + 1][j + 1][0] + dp[i][j][k]) % mod
                        # 判断下一个位置为L的字母的情况
                        if k + 1 <= 2: dp[i + 1][j][k + 1] = (dp[i + 1][j][k + 1] + dp[i][j][k]) % mod
                        # 下一个位置为字母P一定合法所以直接计算即可
                        dp[i + 1][j][0] = (dp[i + 1][j][0] + dp[i][j][k]) % mod
            res = 0
            # 计算有n个字母所有的合法方案, 包含合法的字母A和字母L的情况
            for j in range(2):
                for k in range(3):
                    res = (res + dp[n][j][k]) % mod
            return res

**java代码（232ms）**

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70]: /images/20220829/86c094475deb4f82971ce9303b805393.png