【刷穿 LeetCode】552. 学生出勤记录 II :「记忆化搜索」&「动态规划」&「矩阵快速幂」

简介: 【刷穿 LeetCode】552. 学生出勤记录 II :「记忆化搜索」&「动态规划」&「矩阵快速幂」

网络异常,图片无法展示
|


题目描述



这是 LeetCode 上的 552. 学生出勤记录 II ,难度为 困难


Tag : 「动态规划」、「状态机」、「记忆化搜索」、「矩阵快速幂」、「数学」


可以用字符串表示一个学生的出勤记录,其中的每个字符用来标记当天的出勤情况(缺勤、迟到、到场)。


记录中只含下面三种字符:


  • 'A':Absent,缺勤
  • 'L':Late,迟到
  • 'P':Present,到场


如果学生能够同时满足下面两个条件,则可以获得出勤奖励:


  • 总出勤计,学生缺勤('A')严格 少于两天。
  • 学生不会存在 连续 3 天或 连续 3 天以上的迟到('L')记录。


给你一个整数 n ,表示出勤记录的长度(次数)。请你返回记录长度为 n 时,可能获得出勤奖励的记录情况 数量 。


答案可能很大,所以返回对 10^9 + 7109+7取余的结果。


示例 1:


输入:n = 2
输出:8
解释:
有 8 种长度为 2 的记录将被视为可奖励:
"PP" , "AP", "PA", "LP", "PL", "AL", "LA", "LL" 
只有"AA"不会被视为可奖励,因为缺勤次数为 2 次(需要少于 2 次)。
复制代码


示例 2:


输入:n = 1
输出:3
复制代码


示例 3:


输入:n = 10101
输出:183236316
复制代码


提示:


  • 1 <= n <= 10^5105


基本分析



根据题意,我们知道一个合法的方案中 A 的总出现次数最多为 11 次,L 的连续出现次数最多为 22 次。


因此在枚举/统计合法方案的个数时,当我们决策到某一位应该选什么时,我们关心的是当前方案中已经出现了多少个 A(以决策当前能否填入 A)以及连续出现的 L 的次数是多少(以决策当前能否填入 L)。


记忆化搜索



枚举所有方案的爆搜 DFS 代码不难写,大致的函数签名设计如下:


/**
 * @param u 当前还剩下多少位需要决策
 * @param acnt 当前方案中 A 的总出现次数
 * @param lcnt 当前方案中结尾 L 的连续出现次数
 * @param cur 当前方案
 * @param ans 结果集
 */
void dfs(int u, int acnt, int lcnt, String cur, List<String> ans);
复制代码

实际上,我们不需要枚举所有的方案数,因此我们只需要保留函数签名中的前三个参数即可。

同时由于我们在计算某个 (u, acnt, lcnt)(u,acnt,lcnt) 的方案数时,其依赖的状态可能会被重复使用,考虑加入记忆化,将结果缓存起来。

根据题意,nn 的取值范围为 [0, n][0,n]acntacnt 取值范围为 [0,1][0,1]lcntlcnt 取值范围为 [0, 2][0,2]

代码:

class Solution {
    int mod = (int)1e9+7;
    int[][][] cache;
    public int checkRecord(int n) {
        cache = new int[n + 1][2][3];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j < 2; j++) {
                for (int k = 0; k < 3; k++) {
                    cache[i][j][k] = -1;
                }
            }
        }
        return dfs(n, 0, 0);
    }
    int dfs(int u, int acnt, int lcnt) {
        if (acnt >= 2) return 0;
        if (lcnt >= 3) return 0;
        if (u == 0) return 1;
        if (cache[u][acnt][lcnt] != -1) return cache[u][acnt][lcnt];
        int ans = 0;
        ans = dfs(u - 1, acnt + 1, 0) % mod; // A
        ans = (ans + dfs(u - 1, acnt, lcnt + 1)) % mod; // L
        ans = (ans + dfs(u - 1, acnt, 0)) % mod; // P
        cache[u][acnt][lcnt] = ans;
        return ans;
    }
}
复制代码


  • 时间复杂度:有 O(n * 2 * 3)O(n23) 个状态需要被计算,复杂度为 O(n)O(n)
  • 空间复杂度:O(n)O(n)


状态机 DP



通过记忆化搜索的分析我们发现,当我们在决策下一位是什么的时候,依赖于前面已经填入的 A 的个数以及当前结尾处的 L 的连续出现次数。


也就说是,状态 f[u][acnt][lcnt]f[u][acnt][lcnt] 必然被某些特定状态所更新,或者说由 f[u][[acnt][lcnt]f[u][[acnt][lcnt] 出发,所能更新的状态是固定的。


因此这其实是一个状态机模型的 DP 问题。


根据「更新 f[u][acnt][lcnt]f[u][acnt][lcnt] 需要哪些状态值」还是「从 f[u][acnt][lcnt]f[u][acnt][lcnt] 出发,能够更新哪些状态」,我们能够写出两种方式(方向)的 DP 代码:


一类是从 f[u][acnt][lcnt]f[u][acnt][lcnt] 往回找所依赖的状态;一类是从 f[u][acnt][lcnt]f[u][acnt][lcnt] 出发往前去更新所能更新的状态值。


无论是何种方式(方向)的 DP 实现都只需搞清楚「当前位的选择对 acntacntlcntlcnt 的影响」即可。


代码:


// 从 f[u][acnt][lcnt] 往回找所依赖的状态
class Solution {
    int mod = (int)1e9+7;
    public int checkRecord(int n) {
        int[][][] f = new int[n + 1][2][3];
        f[0][0][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < 2; j++) {
                for (int k = 0; k < 3; k++) {
                    if (j == 1 && k == 0) { // A
                        f[i][j][k] = (f[i][j][k] + f[i - 1][j - 1][0]) % mod;
                        f[i][j][k] = (f[i][j][k] + f[i - 1][j - 1][1]) % mod;
                        f[i][j][k] = (f[i][j][k] + f[i - 1][j - 1][2]) % mod;
                    }
                    if (k != 0) { // L
                        f[i][j][k] = (f[i][j][k] + f[i - 1][j][k - 1]) % mod;
                    }
                    if (k == 0) { // P
                        f[i][j][k] = (f[i][j][k] + f[i - 1][j][0]) % mod;
                        f[i][j][k] = (f[i][j][k] + f[i - 1][j][1]) % mod;
                        f[i][j][k] = (f[i][j][k] + f[i - 1][j][2]) % mod;
                    }
                }
            }
        }
        int ans = 0;
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 3; k++) {
                ans += f[n][j][k];
                ans %= mod;
            }
        }
        return ans;
    }
}
复制代码


// 从 f[u][acnt][lcnt] 出发往前去更新所能更新的状态值
class Solution {
    int mod = (int)1e9+7;
    public int checkRecord(int n) {
        int[][][] f = new int[n + 1][2][3];
        f[0][0][0] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 2; j++) {
                for (int k = 0; k < 3; k++) {
                    if (j != 1) f[i + 1][j + 1][0] = (f[i + 1][j + 1][0] + f[i][j][k]) % mod; // A
                    if (k != 2) f[i + 1][j][k + 1] = (f[i + 1][j][k + 1] + f[i][j][k]) % mod; // L
                    f[i + 1][j][0] = (f[i + 1][j][0] + f[i][j][k]) % mod; // P
                }
            }
        }
        int ans = 0;
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 3; k++) {
                ans += f[n][j][k];
                ans %= mod;
            }
        }
        return ans;
    }
}
复制代码


  • 时间复杂度:O(n)O(n)
  • 空间复杂度:O(n)O(n)


矩阵快速幂



之所以在动态规划解法中强调更新状态的方式(方向)是「往回」还是「往前」,是因为对于存在线性关系(同时又具有结合律)的递推式,我们能够通过「矩阵快速幂」来进行加速。


矩阵快速幂的基本分析之前在 (题解) 1137. 第 N 个泰波那契数 详细讲过。


由于 acntacntlcntlcnt 的取值范围都很小,其组合的状态只有 2 * 3 = 623=6 种,我们使用 idx = acnt * 3 + lcntidx=acnt3+lcnt 来代指组合(通用的二维转一维方式):


  • idx = 0idx=0acnt = 0、lcnt = 0acnt=0lcnt=0
  • idx = 1idx=1acnt = 1、lcnt = 0acnt=1lcnt=0

...

  • idx = 5idx=5acnt = 1、lcnt = 2acnt=1lcnt=2


最终答案为 ans = \sum_{idx = 0}^{5} f[n][idx]ans=idx=05f[n][idx],将答案依赖的状态整理成列向量:


g[n] = \begin{bmatrix} f[n][0]\\ f[n][1]\\ f[n][2]\\ f[n][3]\\ f[n][4]\\ f[n][5] \end{bmatrix}g[n]=f[n][0]f[n][1]f[n][2]f[n][3]f[n][4]f[n][5]


根据状态机逻辑,可得:


g[n] = \begin{bmatrix} f[n][0]\\ f[n][1]\\ f[n][2]\\ f[n][3]\\ f[n][4]\\ f[n][5] \end{bmatrix} = \begin{bmatrix} f[n - 1][0] * 1 + f[n - 1][1] * 1 + f[n - 1][2] * 1 + f[n - 1][3] * 0 + f[n - 1][4] * 0 + f[n - 1][5] * 0\\ f[n - 1][0] * 1 + f[n - 1][1] * 0 + f[n - 1][2] * 0 + f[n - 1][3] * 0 + f[n - 1][4] * 0 + f[n - 1][5] * 0\\ f[n - 1][0] * 0 + f[n - 1][1] * 1 + f[n - 1][2] * 0 + f[n - 1][3] * 0 + f[n - 1][4] * 0 + f[n - 1][5] * 0\\ f[n - 1][0] * 1 + f[n - 1][1] * 1 + f[n - 1][2] * 1 + f[n - 1][3] * 1 + f[n - 1][4] * 1 + f[n - 1][5] * 1\\ f[n - 1][0] * 0 + f[n - 1][1] * 0 + f[n - 1][2] * 0 + f[n - 1][3] * 1 + f[n - 1][4] * 0 + f[n - 1][5] * 0\\ f[n - 1][0] * 0 + f[n - 1][1] * 0 + f[n - 1][2] * 0 + f[n - 1][3] * 0 + f[n - 1][4] * 1 + f[n - 1][5] * 0 \end{bmatrix}g[n]=f[n][0]f[n][1]f[n][2]f[n][3]f[n][4]f[n][5]=f[n1][0]1+f[n1][1]1+f[n1][2]1+f[n1][3]0+f[n1][4]0+f[n1][5]0f[n1][0]1+f[n1][1]0+f[n1][2]0+f[n1][3]0+f[n1][4]0+f[n1][5]0f[n1][0]0+f[n1][1]1+f[n1][2]0+f[n1][3]0+f[n1][4]0+f[n1][5]0f[n1][0]1+f[n1][1]1+f[n1][2]1+f[n1][3]1+f[n1][4]1+f[n1][5]1f[n1][0]0+f[n1][1]0+f[n1][2]0+f[n1][3]1+f[n1][4]0+f[n1][5]0f[n1][0]0+f[n1][1]0+f[n1][2]0+f[n1][3]0+f[n1][4]1+f[n1][5]0


我们令:


mat = \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}mat=110100101100100100000110000101000100


根据「矩阵乘法」即有:


g[n] = mat * g[n - 1]g[n]=matg[n1]


起始时,我们只有 g[0]g[0],根据递推式得:


g[n] = mat * mat * ... * mat * g[0]g[n]=matmat...matg[0]


再根据矩阵乘法具有「结合律」,最终可得:


g[n] = mat^n * g[0]g[n]=matng[0]


计算 mat^nmatn 可以套用「快速幂」进行求解。


代码:


class Solution {
    int N = 6;
    int mod = (int)1e9+7;
    long[][] mul(long[][] a, long[][] b) {
        int r = a.length, c = b[0].length, z = b.length;
        long[][] ans = new long[r][c];
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                for (int k = 0; k < z; k++) {
                    ans[i][j] += a[i][k] * b[k][j];
                    ans[i][j] %= mod;
                }
            }
        }
        return ans;
    }
    public int checkRecord(int n) {
        long[][] ans = new long[][]{
            {1}, {0}, {0}, {0}, {0}, {0}
        };
        long[][] mat = 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}
        };
        while (n != 0) {
            if ((n & 1) != 0) ans = mul(mat, ans);
            mat = mul(mat, mat);
            n >>= 1;
        }
        int res = 0;
        for (int i = 0; i < N; i++) {
            res += ans[i][0];
            res %= mod;
        }
        return res;
    } 
}
复制代码


  • 时间复杂度:O(\log{n})O(logn)
  • 空间复杂度:O(1)O(1)


最后



这是我们「刷穿 LeetCode」系列文章的第 No.552 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。


在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。


为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:github.com/SharingSour…


在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

相关文章
|
3月前
|
存储 算法 NoSQL
LeetCode第73题矩阵置零
文章介绍了LeetCode第73题"矩阵置零"的解法,通过使用矩阵的第一行和第一列作为标记来记录哪些行或列需要置零,从而在不增加额外空间的情况下解决问题。
LeetCode第73题矩阵置零
|
19天前
|
算法 索引
LeetCode(搜索插入位置)
如何使用二分查找算法来解决LeetCode上的“搜索插入位置”问题,确保时间复杂度为O(log n),并提供了详细的代码实现和分析。
13 2
|
18天前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
12 0
Leetcode第三十三题(搜索旋转排序数组)
|
18天前
【LeetCode 39】700.二叉搜索树中的搜索
【LeetCode 39】700.二叉搜索树中的搜索
12 0
|
18天前
|
算法 C++
Leetcode第59题(螺旋矩阵2)
这篇文章介绍了解决LeetCode第59题“螺旋矩阵II”的算法,通过C++编程实现按顺时针顺序填充一个n x n的正方形矩阵。
14 0
|
3月前
|
算法
LeetCode第81题搜索旋转排序数组 II
文章讲解了LeetCode第81题"搜索旋转排序数组 II"的解法,通过二分查找算法并加入去重逻辑来解决在旋转且含有重复元素的数组中搜索特定值的问题。
LeetCode第81题搜索旋转排序数组 II
|
3月前
|
算法
LeetCode第74题搜索二维矩阵
文章讲解了LeetCode第74题"搜索二维矩阵"的解决方案,利用二分搜索法将问题简化,并通过数学转换找到二维矩阵中的对应元素,展示了将二维问题转化为一维问题的解题技巧。
LeetCode第74题搜索二维矩阵
|
3月前
|
算法
LeetCode第35题搜索插入位置
这篇文章介绍了LeetCode第35题"搜索插入位置"的解题方法,通过使用二分查找法,高效地找到在有序数组中插入一个目标数的最佳位置。
LeetCode第35题搜索插入位置
|
3月前
|
算法
LeetCode第33题搜索旋转排序数组
这篇文章介绍了LeetCode第33题"搜索旋转排序数组"的解题方法,通过使用二分查找法并根据数组的有序性质调整搜索范围,实现了时间复杂度为O(log n)的高效搜索算法。
LeetCode第33题搜索旋转排序数组
|
3月前
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
49 6