LeetCode551&552.学生出勤记录：「状态DP」&「矩阵快速幂」

浏览次数 : 次 2022-01-18

博文字数统计 : 3.8k字 | 阅读所需时长 : 17分

× 文章目录

1. LeetCode551&552.学生出勤记录：「状态DP」&「矩阵快速幂」
2. \end{gathered}

LeetCode551：学生出勤记录I
- 时间：2022-01-18
- 力扣难度：Easy
- 个人难度：Easy
- 数据结构：字符串
- 算法：模拟
LeetCode552：学生出勤记录II
- 时间：2022-01-18
- 力扣难度：Hard
- 个人难度：Hard+
- 数据结构：字符串
- 算法：状态机、动态规划、递归、矩阵快速幂

LeetCode551&552.学生出勤记录：「状态DP」&「矩阵快速幂」

1. 前置题目：LC551。学生出勤记录I

题目：原题链接
- 给你一个字符串 s 表示一个学生的出勤记录，其中的每个字符用来标记当天的出勤情况。记录中只含下面三种字符：
  - ‘A’：Absent，缺勤
  - ‘L’：Late，迟到
  - ‘P’：Present，到场
- 如果学生能够同时满足下面两个条件，则可以获得出勤奖励：
  - 按总出勤计，学生缺勤（’A’）严格少于两天。
  - 学生不会存在连续 3 天或连续 3 天以上的迟到（’L’）记录。
- 如果学生可以获得出勤奖励，返回 true ；否则，返回 false 。
- 1 <= s.length <= 1000
- s[i] 为 'A'、'L' 或 'P'
输入输出规范：
- 输入：字符串
- 输出：是否可以得到奖励
输入输出示例
- 输入：s = “PPALLL”
- 输出：false

题解：直接根据规则进行模拟，运用双指针

public boolean checkRecord(String s) {
    if (s == null || s.length() == 0) return false;
    int n = s.length();
    int absent = 0;
    for (int i = 0; i < n; i++) {
        if (s.charAt(i) == 'A') {
            absent++;
            if (absent >= 2) return false;
        }else if (s.charAt(i) == 'L') {
            int j = i + 1;
            while (j < n && s.charAt(j) == 'L') {
                if(j - i + 1 >= 3) return false;
                j++;
            }
            i = j - 1; // 跳过已经判断的字符
        }
    }
    return true;
}

题解：运用字符串的API

1
2
3

public boolean checkRecord(String s) {
    return !s.contains("LLL") && s.indexOf("A") == s.lastIndexOf("A");
}

复杂度分析：n 是字符串的长度
- 时间复杂度：$O(n)$
- 空间复杂度：$O(1)$

2. 题目描述：LC552.学生出勤记录II

题目：原题链接
- 基本的题目要求与LC551完全相同，只是求解的内容发生了变化
- 给你一个整数 n ，表示出勤记录的长度、次数
- 请你返回记录长度为 n 时，可能获得出勤奖励的记录情况数量。
- 答案可能很大，所以返回对 109 + 7 取余的结果。
- 1 <= n <= 10^5
输入输出规范
- 输入：整型 n，表示记录的长度
- 输出：整型，表示可以获奖的次数
输入输出示例
- 输入：n = 2
- 输出：8
- 解释：有 8 种长度为 2 的记录将被视为可奖励：”PP” , “AP”, “PA”, “LP”, “PL”, “AL”, “LA”, “LL”
- 输入：n = 10101
- 输出：183236316

3. 方法一：DFS & 记忆化

思路
- 本题相当于构造一个长度为 n 的字符串，每个字符都可以是 P、A、L 中的一个，但是有两个限制：A 不能超过两个，L 不能连续三个或以上
- 因此可以直接按照DFS和回溯的思想，逐个位置填充字符，并记录 A 和连续 L 的个数，可以作为全局变量，或者作为DFS方法的参数
- 每次DFS递归的时候都分别判断下一个字符使用 A、P、L 的情况
- 注意：因为对于 L 的判断是要连续三次才算，所以对于下一个字符使用 A 或 P 时，要将 L 的计数器重置为0

题解：暴力DFS，TLE超时

final int MOD = (int) 1e9 + 7;

// 方法1. DFS
public int checkRecord(int n) {
    return dfs(0, n, 0, 0);
}

private int dfs(int size, int n, int absent, int late) {
    if (size == n) return 1;
    int res = 0;
    // 放置 P
    res += dfs(size + 1, n, absent, 0);
    res %= MOD;
    // 放置 A
    if (absent < 1) {
        res += dfs(size + 1, n, absent + 1, 0);
        res %= MOD;
    }
    // 放置 L
    if (late < 2) {
        res += dfs(size + 1, n, absent, late + 1);
        res %= MOD;
    }
    return res;
}

复杂度分析：n 是输入的长度
- 时间复杂度：$O(3^n)$，暴搜相当于遍历了所有情况
- 空间复杂度：$O(n)$

题解：DFS & 记忆化

// 方法1 优化. 记忆化DFS
public int checkRecord(int n) {
    int[][][] memo = new int[n][2][3]; // 长度、A的个数、末尾L的连续个数
    return dfs(0, n, 0, 0, memo);
}

private int dfs(int size, int n, int absent, int late, int[][][] memo) {
    if (size == n) return 1;
    if (memo[size][absent][late] != 0) return memo[size][absent][late];
    int res = 0;
    // 放置 P
    res += dfs(size + 1, n, absent, 0, memo);
    res %= MOD;
    // 放置 A
    if (absent < 1) {
        res += dfs(size + 1, n, absent + 1, 0, memo);
        res %= MOD;
    }
    // 放置 L
    if (late < 2) {
        res += dfs(size + 1, n, absent, late + 1, memo);
        res %= MOD;
    }
    memo[size][absent][late] = res;
    return res;
}

复杂度分析(优化后)：n 是输入的长度
- 时间复杂度：$O(n)$，记忆化可以使得搜素过程不重复
- 空间复杂度：$O(n)$

4. 方法二：动态规划

思路：状态机 & 动态规划
- 本题的状态之间也存在着深层的递推的关系，不容易确定DP数组定义及状态转移方程的过程，这里进行简要分析
- 首先，因为求解的是个数，所以DP数组至少需要一个维度来表示当前的长度，其次，由于题目的规则限制，我们可以发现，符合我们结果的字符串中一定只有0或1个 A，0~2个连续的 L，即同一长度下，应该有六种状态
- DP数组的含义：dp[i][j][k]：表示长度为 i 的具有 j 个 A，且末尾只有 k 个连续 L 的序列的个数
  - i 表示序列当前的长度
  - j 表示 A 的个数，取值范围是 [0, 1]
  - k 表示序列末尾处 L 的连续个数，取值范围是 [0, 3)
  - 其中，k 表示的是末尾处，而不是整个序列中，这是因为DP数组表示合法的序列个数，所以对于 i-1 长度时，其序列只有在末尾一直追加 L 时才会不合法 (这里先不考虑 A的因素)
- 边界条件：初始的六种状态中，因为此时只有一个字符，所以其实只存在三种状态，这三种初始化为 1
  - dp[0][0][0] = 1
  - dp[0][1][0] = 1
  - dp[0][0][1] = 1
- 状态转移方程：只能为前一个长度下六种状态末尾分别添加 A、P、L 构成
  - dp[i][0][0] = dp[i-1][0][0] + dp[i-1][0][1] + dp[i-1][0][2]
  - dp[i][0][1] = dp[i-1][0][0]
  - dp[i][0][2] = dp[i-1][0][1]
  - dp[i][1][0] = dp[i-1][0][0] + dp[i-1][0][1] + dp[i-1][0][2] + dp[i-1][1][0] + dp[i-1][1][1] + dp[i-1][1][2]
  - dp[i][1][1] = dp[i-1][1][0]
  - dp[i][1][2] = dp[i-1][1][1]
图解状态转移方程

题解：三维DP

// 方法2. 状态机DP
public int checkRecord(int n) {
    long[][][] dp = new long[n][2][3]; // 长度、A的个数、末尾L的连续个数
    dp[0][0][0] = 1;
    dp[0][1][0] = 1;
    dp[0][0][1] = 1;

    for (int i = 1; i < n; i++) {
        dp[i][0][0] = (dp[i - 1][0][0] + dp[i - 1][0][1] + dp[i - 1][0][2]) % MOD; // 添加 P
        dp[i][0][1] = dp[i - 1][0][0] % MOD; // 添加 L
        dp[i][0][2] = dp[i - 1][0][1] % MOD; // 添加 L
        // 前三个添加 A  & 后三个添加 P
        dp[i][1][0] = (dp[i - 1][0][0] + dp[i - 1][0][1] + dp[i - 1][0][2] + dp[i - 1][1][0] + dp[i - 1][1][1] + dp[i - 1][1][2]) % MOD; 
        dp[i][1][1] = dp[i - 1][1][0] % MOD; // 添加 L
        dp[i][1][2] = dp[i - 1][1][1] % MOD; // 添加 L
    }
    int count = 0;
    for (int i = 0; i < dp[0].length; i++) {
        for (int j = 0; j < dp[0][0].length; j++) {
            count += dp[n - 1][i][j];
            count %= MOD;
        }
    }
    return count;
}

复杂度分析(优化后)：n 是输入的长度
- 时间复杂度：$O(n)$，只需要遍历一次序列长度
- 空间复杂度：$O(2Cn)$，C 为同一时刻下的状态个数，本题中 C = 6
思考与优化：空间优化
- 可以发现，DP数组在计算过程中，只依赖与前一个时刻的所有状态，即dp[i][j][k]只与dp[i-1][j][k]有关
- 所以可以进行空间优化，无需存储上一时刻之前的状态，只需要一个二维DP数组，dp[i][j]表示序列长度为 i 时的六种状态，j 的取值范围是 [0,6)，这时要规定好六种状态的顺序，此处与三维DP时的顺序保持一致
- 进一步的，可以优化为一维DP，即直接使用六个变量来存储状态即可，此时只需要一个辅助数组来保存上一时刻的状态，否则会导致变量在使用前被更新
- 这种方式可以使用滚动数组简单实现，创建一个2×6的数组，第一行为当前状态，第二行为上一时刻状态，在遍历过程中动态更新

题解：二维优化

// 方法2 优化. 空间压缩，三维DP 优化为 二维DP
public int checkRecord(int n) {
    long[][] dp = new long[n][6]; // 长度、六种状态分别为 0A0L、0A1L、0A2L、1A0L、1A1L、1A2L
    dp[0][0] = 1;
    dp[0][1] = 1;
    dp[0][3] = 1;

    for (int i = 1; i < n; i++) {
        dp[i][0] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % MOD;
        dp[i][1] = dp[i - 1][0] % MOD;
        dp[i][2] = dp[i - 1][1] % MOD;
        dp[i][3] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][3] + dp[i - 1][4] + dp[i - 1][5]) % MOD;
        dp[i][4] = dp[i - 1][3] % MOD;
        dp[i][5] = dp[i - 1][4] % MOD;
    }
    int count = 0;
    for (int i = 0; i < dp[0].length; i++) {
        count += dp[n - 1][i];
        count %= MOD;
    }
    return count;
}

题解：一维优化：状态机 & 滚动数组

// 方法2 优化. 空间压缩，三维DP 优化为 一维DP，状态机 + 滚动数组
public int checkRecord(int n) {
    if(n == 1) return 3;
    long[][] dp = new long[2][6]; // 当前长度、六种状态分别为 0A0L、0A1L、0A2L、1A0L、1A1L、1A2L
    // 辅助数组 初始化即可
    dp[1][0] = 1;
    dp[1][1] = 1;
    dp[1][3] = 1;

    for (int i = 1; i < n; i++) {
        dp[0][0] = (dp[1][0] + dp[1][1] + dp[1][2]) % MOD;
        dp[0][1] = dp[1][0] % MOD;
        dp[0][2] = dp[1][1] % MOD;
        dp[0][3] = (dp[1][0] + dp[1][1] + dp[1][2] + dp[1][3] + dp[1][4] + dp[1][5]) % MOD;
        dp[0][4] = dp[1][3] % MOD;
        dp[0][5] = dp[1][4] % MOD;
        // 滚动辅助数组
        /*for (int j = 0; j < dp[0].length; j++) {
                dp[1][j] = dp[0][j];
            }*/
        System.arraycopy(dp[0], 0, dp[1], 0, dp[0].length);
    }
    int count = 0;
    for (long cnt : dp[0]) {
        count += cnt;
        count %= MOD;
    }
    return count;

复杂度分析(优化后)：n 是输入的长度
- 时间复杂度：$O(n)$，只需要遍历一次序列长度
- 空间复杂度：$O(2*C)$，C 为同一时刻下的状态个数，本题中 C = 6

5. 方法三：矩阵快速幂

思路：矩阵乘法 & 快速幂
- 对于状态机DP问题而言，如果状态转移的过程可以表示为线性的叠加，就可以转换为矩阵计算来提高效率
- 为了求出dp[n]，状态DP一般都需要遍历次，即线性的时间复杂度 $O(n)$，而矩阵计算可以通过矩阵具有结合律的性质来将复杂度优化到对数级 $O(logn)$
- 这种方法可以正确求解结果的根本原因是矩阵乘法，具体推导涉及到线性代数的知识，而复杂度为对数级是因为在求解矩阵时使用了快速幂算法
快速幂
- 快速幂是用于求解 x 的 n 次幂问题的一种算法，通过奇偶次幂的判断并分类讨论，将线性复杂度二分为对数复杂度
- 具体而言，是在偶次幂时进行矩阵平方并将幂除2，奇次幂时进行矩阵与初始值相乘并赋值给初始值
矩阵乘法
- 矩阵乘法要求前一个矩阵的列数等于后一个矩阵的行数
- 相乘得到的矩阵的行数与前一个矩阵行数相等，列数与后一个矩阵列数相等
状态机DP转化为矩阵乘法的过程，以本题为例
- 对于本题，根据状态转移方程以及矩阵乘法的性质，可以得到
  $$
  \begin{gathered}
  \begin{bmatrix}
  T_{i,0}
  \T_{i,1}
  \T_{i,2}
  \T_{i,3}
  \T_{i,4}
  \T_{i,5}
  \end{bmatrix}
  
  \end{gathered}
  \begin{gathered}
  \begin{bmatrix}
  T_{i - 1,0}+T_{i - 1,1}+T_{i - 1,2} \
  T_{i - 1,0} \
  T_{i - 1,1} \
  T_{i - 1,0}+T_{i - 1,1}+T_{i - 1,2}++T_{i - 1,3}+T_{i - 1,4} \
  T_{i - 1,3} \
  T_{i - 1,4}
  \end{bmatrix}
  \end{gathered}=
  
  \begin{gathered}
  \begin{bmatrix}
  1 & 1 & 1 & 0 & 0 & 0\
  1 & 0 & 0 & 0 & 0 & 0\
  0 & 1 & 0 & 0 & 0 & 0\
  1 & 1 & 1 & 1 & 1 & 1\
  0 & 0 & 0 & 1 & 0 & 0\
  0 & 0 & 0 & 0 & 1 & 0\
  \end{bmatrix}*
  \end{gathered}
  \begin{gathered}
  \begin{bmatrix}
  T_{i-1,0}
  \ T_{i-1,1}
  \ T_{i-1,2}
  \ T_{i-1,3}
  \ T_{i-1,4}
  \ T_{i-1,5}
  \end{bmatrix}
  \end{gathered}
  $$
- 其中，我们可以得到一个状态转移的系数矩阵 M：
  $$
  M=\begin{gathered}
  \begin{bmatrix}
  1 & 1 & 1 & 0 & 0 & 0\
  1 & 0 & 0 & 0 & 0 & 0\
  0 & 1 & 0 & 0 & 0 & 0\
  1 & 1 & 1 & 1 & 1 & 1\
  0 & 0 & 0 & 1 & 0 & 0\
  0 & 0 & 0 & 0 & 1 & 0\
  \end{bmatrix}
  \end{gathered}
  $$
- 将矩阵形式递推到 $T(n)$，根据矩阵的结合律，可以得到：
$$
\begin{gathered}
\begin{bmatrix}
T_{i,0}
\T_{i,1}
\T_{i,2}
\T_{i,3}
\T_{i,4}
\T_{i,5}
\end{bmatrix}
\end{gathered}
= M*
\begin{gathered}
\begin{bmatrix}
T_{i-1,0}
\T_{i-1,1}
\T_{i-1,2}
\T_{i-1,3}
\T_{i-1,4}
\T_{i-1,5}
\end{bmatrix}
\end{gathered}=
M^{n-1}*
\begin{gathered}
\begin{bmatrix}
T_{0,0}
\T_{0,1}
\T_{0,2}
\T_{0,3}
\T_{0,4}
\T_{0,5}
\end{bmatrix}
\end{gathered}=M^{n-1}*
\begin{gathered}
\begin{bmatrix}
1
\ 1
\ 0
\ 1
\ 0
\ 0
\end{bmatrix}
\end{gathered}
$$
- 所以就将整个过程化简为求矩阵 M 的 n-1 次幂问题，实际上就是矩阵乘法，结合快速幂算法，求出矩阵 M 后，与初始状态做矩阵乘法，得到的结果矩阵的第一个元素就是我们要求的结果

题解：初始数组使用初始值填充，一维

// 方法3. 矩阵快速幂
public int checkRecord(int n) {
    long[][] ini = new long[][]{
        {1}, {1}, {0}, {1}, {0}, {0}
    };
    long[][] matrix = new long[][]{
        {1, 1, 1, 0, 0, 0},
        {1, 0, 0, 0, 0, 0},
        {0, 1, 0, 0, 0, 0},
        {1, 1, 1, 1, 1, 1},
        {0, 0, 0, 1, 0, 0},
        {0, 0, 0, 0, 1, 0},
    };

    int x = n - 1;
    while (x > 0) {
        if ((x & 1) == 1) ini = mul(matrix, ini);
        matrix = mul(matrix, matrix);
        x >>= 1;
    }
    int count = 0;
    for (long[] cnt : ini) {
        count += cnt[0];
        count %= MOD;
    }
    return count;

}

private long[][] mul(long[][] matrixA, long[][] matrixB) {
    int row = matrixA.length, col = matrixB[0].length;
    int size = matrixB.length;
    long[][] res = new long[row][col];
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            for (int k = 0; k < size; k++) {
                res[i][j] += matrixA[i][k] * matrixB[k][j];
                res[i][j] %= MOD;
            }
        }
    }
    return res;
}

复杂度分析：n 是输入的长度
- 时间复杂度：$O(C^3*logn)$，C 是状态个数，本题 C = 6
- 空间复杂度：$O(C^2)$

本文作者： Chthollists
发布时间： 2022-01-18 18:02:46
最后更新： 2022-01-21 23:09:05
本文标题： LeetCode551&552.学生出勤记录：「状态DP」&「矩阵快速幂」
本文链接： https://chthollists.github.io/post/5806813.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处！

LeetCode551&552.学生出勤记录：「状态DP」&「矩阵快速幂」

1. 前置题目：LC551。学生出勤记录I

2. 题目描述：LC552.学生出勤记录II

3. 方法一：DFS & 记忆化

4. 方法二：动态规划

5. 方法三：矩阵快速幂

\end{gathered}