动态规划（二十）学生出勤记录

本文主要是介绍动态规划（二十）学生出勤记录，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

问题描述

给你一个整数 \(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/

这篇关于动态规划（二十）学生出勤记录的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！