动态规划(二十)学生出勤记录

问题描述

给你一个整数 \(n\) 表示学生出勤的天数,在每一天学生的可能出勤情况为:'A'(缺勤)、'L'(迟到)、'P'(正常出勤)。

如果学生要获取出勤奖励,需要同时满足以下几个条件:

  • 在 \(n\) 天中缺勤的天数不能超过两天
  • 在 \(n\) 天中,不能有连续三天出现迟到的情况

现要求得在 \(n\) 天内,有多少种可能的出勤情况是能够获得出勤奖励。由于可能的情况数量会很大,因此要对结果对 \(1e9 + 7\) 求摸

\(n\) 的取值范围:\(1<=n<=10^5\)

解决思路

  • DFS

    首先尝试使用一般的 DFS 方式解决这个问题,对于每一天的出勤情况,只能是 'A'、'L'、'P' 中的一种,因此只需要从开始位置不断遍历每个位置的可能情况,找到符合条件的出勤情况进行累加即可

    特别地,对于不满足获奖条件的情况,可以通过变量 \(aCnt\) 表示当前出勤记录中 'A' 的数量,变量 \(lCnt\) 表示当前位置连续的 'L' 数量,对于不满足条件的出勤记录,可以较早地退出搜索

  • 带记忆化的 DFS

    在搜索过程中会重复计算之前已经计算过的数据,因此这会浪费大量的时间。为了解决这个问题,可以存储之前已经计算过的结果,从而降低算法的时间复杂度。

    如何缓存之前已经计算过的结果是一个有挑战的问题,因为由于存在三种状态,而每个状态内又有几种状态,因此在这里使用三维数组会是一个更好的解决方案。通过定义 \(cache[i][j][k]\) 表示在 \(i\) 位置,'A' 状态为 \(j\)、‘L’ 状态为 \(k\) 的情况下存在的能够获奖的可能数

  • 动态规划

    有了上文 \(cache[i][j][k]\) 的存在,现在可以将这个通过动态规划的方式来实现了(转换的过程比较麻烦)

    定义 \(dp[i][j][k]\) 表示,'A' 状态为 \(j\)、‘L’ 状态为 \(k\) 的情况下存在的能够获奖的可能数

    具体地,对应的转移函数如下:

    • 当位置 \(i\) 的出勤情况为 'P' 时,对应的转移函数如下所示

    \[dp[i][j][0] = dp[i][j][0] + \sum_{k=0}^{2}dp[i - 1][j][k] \]

    • 当位置 \(i\) 的出勤情况为 'A' 时,对应的转移函数

      \[dp[i][1][0] = dp[i][1][0] + \sum_{k=0}^{2} dp[i - 1][0][k] \]

    • 当位置 \(i\) 的出勤情况为 'L' 时,对应的转移函数

      \[dp[i][j][k] = dp[i][j][k] + dp[i - 1][j][k - 1]\quad 1\leq k \leq 2 \]

  • 矩阵快速幂

    由上面的动态规划,可以得出可能的状态为 \(dp[i][j][k]\),由于 \(0\leq j \leq 1\),\(0\leq k \leq 2\),因此,可能的状态可以简化为 \(dp[i][6]\),因此最终的答案为:

    \[ans = \sum_{idx=0}^{6}dp[n][idx] \]

    将其转换为列向量:

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

    由转换逻辑:

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

    定义矩阵 \(mat\)

    \[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} \]

    因此:

    \[\begin{equation} \begin{split} g[n]&= mat*g[n-1] \\ &= mat*mat*……g[0] \\ &=mat^n*g[0] \end{split} \end{equation} \]

    通过矩阵快速幂的方式,可以在 \(O(log_2n)\) 的时间复杂读内完成

实现

  • DFS

    class Solution {
        int mod = (int) 1e9 + 7;
        int n;
    
        public int checkRecord(int n) {
            this.n = n;
    
            return dfs(0, 0, 0);
        }
    
        /**
        * @param idx:当前处理的位置
        * @param aCnt:当期的出勤记录中 'A' 的数量
        * @param lCnt:当前的出勤记录中最近连续的 'L' 的数量
        */
        private int dfs(int idx, int aCnt, int lCnt) {
            if (aCnt >= 2) return 0;
            if (lCnt >= 3) return 0;
            if (idx == n) return 1;
    
            int cnt = 0;
            cnt += dfs(idx + 1, aCnt + 1, 0); // 当前位置为 'A'
            cnt %= mod;
            cnt += dfs(idx + 1, aCnt, lCnt + 1); // 当前位置为 'L'
            cnt %= mod;
            cnt += dfs(idx + 1, aCnt, 0); // 当前位置为 'P'
            cnt %= mod;
    
            return cnt;
        }
    }
    

    复杂度分析:

    ​ 时间复杂度:对于每个位置都需要进行搜索,因此时间复杂度为 \(O(3^n)\)

    ​ 空间复杂度:忽略由于递归带来的栈的开销,空间复杂度为 \(O(1)\)

  • 带记忆化的 DFS

    class Solution {
        int mod = (int) 1e9 + 7;
        int n;
        int[][][] cache; // 存储中间计算结果的缓存
    
        public int checkRecord(int n) {
            this.n = n;
            this.cache = new int[n][2][3];
    
            // 初始化每个元素为 -1,表示这个元素还没有被访问过
            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(0, 0, 0);
        }
    
        private int dfs(int idx, int aCnt, int lCnt) {
            if (aCnt >= 2) return 0;
            if (lCnt >= 3) return 0;
            if (idx == n) return 1;
    
            if (cache[idx][aCnt][lCnt] != -1)
                return cache[idx][aCnt][lCnt];
    
            cache[idx][aCnt][lCnt] = 0; // 一旦被访问,首先将这个位置的计算结果置为 0,表示这个位置的结果已经被计算过了
    
            cache[idx][aCnt][lCnt] += dfs(idx + 1, aCnt + 1, 0); // 当前位置为 'A'
            cache[idx][aCnt][lCnt] %= mod;
    
            cache[idx][aCnt][lCnt] += dfs(idx + 1, aCnt, lCnt + 1); // 当前位置为 'L'
            cache[idx][aCnt][lCnt] %= mod;
    
            cache[idx][aCnt][lCnt] += dfs(idx + 1, aCnt, 0); // 当前位置为 'P'
            cache[idx][aCnt][lCnt] %= mod;
    
            return cache[idx][aCnt][lCnt];
        }
    }
    

    复杂度分析:

    ​ 时间复杂度:总共需要枚举 \(n*2*3\) 个状态,因此时间复杂度为 \(O(n)\)

    ​ 空间复杂度:需要使用 \(n*2*3\) 的额外空间来记录中间的计算结果,因此空间复杂度为 \(O(n)\)

  • 动态规划

    class Solution {
        int mod = (int) 1e9 + 7;
    
        public int checkRecord(int n) {
            int[][][] dp = new int[n + 1][2][3];
    
            dp[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) {
                        /*
                        	当前位置为 'A' 的情况,因为当前位置插入了 'A',因此会重置 'L' 的连续数为 0,因此 k 也为 0
                        */
                        if (j == 1 && k == 0) {
                            dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j - 1][0]) % mod;
                            dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j - 1][1]) % mod;
                            dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j - 1][2]) % mod;
                        }
                        
                        /*
                        	当前位置为 'L' 的情况,需要统计连续的 'L' 数,因此需要从 k - 1 的 'L' 数转换过来
                        */
                        if (k != 0) {
                            dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k - 1]) % mod;
                        }
                        
                        /*
                        	当前位置为 'P' 的情况,这种情况下也会重置 'L' 的连续数,因此此时的 k 也必须为 0
                        */
                        if (k == 0) {
                            dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][0]) % mod;
                            dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][1]) % mod;
                            dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][2]) % mod;
                        }
                    }
                }
            }
    
            int ans = 0;
            // 累加最后一个位置三种情况的可能数,即为最终的可能数
            for (int j = 0; j < 2; ++j) {
                for (int k = 0; k < 3; ++k) {
                    ans += dp[n][j][k];
                    ans %= mod;
                }
            }
    
            return ans;
        }
    }
    

    复杂度分析:

    ​ 时间复杂度:\(O(n)\)

    ​ 空间复杂度:\(O(n)\)

  • 矩阵快速幂

    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;
        } 
    }
    

    复杂度分析:

    ​ 时间复杂度:使用矩阵快速幂的的时间复杂度为 \((long_2n)\),其它操作的时间复杂度为 \(O(1)\),因此总的时间复杂度为 \(O(long_2n)\)

    ​ 空间复杂度:\(O(1)\)

参考:

[1]https://leetcode-cn.com/problems/student-attendance-record-ii/solution/gong-shui-san-xie-yi-ti-san-jie-ji-yi-hu-fdfx/

上一篇:搜索了一下电脑上编程相关的 pdf, 看有你需要的吗?


下一篇:Delphi 7拦截滚轮事件不响应滚轮的上下滚动