DP

  1. class Solution {
  2. private:
  3.     static constexpr int CEIL = 1000000007;
  4. public:
  5.     int checkRecord(int n) {
  6.         vector<vector<long long> > dp(n, vector<long long>(6, 0));
  7.         // dp[i][0~2]表示在第i天，总A数为0，连续L数为0/1/2时的总组合数，
  8.         // dp[i][3~5]表示在第i天，总A数为1，连续L数为0/1/2时的总组合数
  10.         dp[0][0] = 1; // 第一天为P
  11.         dp[0][1] = 1; // 第一天为L
  12.         dp[0][3] = 1; // 第一天为A
  13.         for (int i = 1; i < n; ++i) {
  14.             // 第i天为P
  15.             for (int j = 0; j < 3; ++j) {
  16.                 dp[i][0] = (dp[i][0] + dp[i - 1][j]) % CEIL;
  17.             }
  18.             for (int j = 3; j < 6; ++j) {
  19.                 dp[i][3] = (dp[i][3] + dp[i - 1][j]) % CEIL;
  20.             }
  22.             // 第i天为A
  23.             for (int j = 0; j < 3; ++j) {
  24.                 dp[i][3] = (dp[i][3] + dp[i - 1][j]) % CEIL;
  25.             }
  27.             // 第i天为L
  28.             dp[i][1] = (dp[i][1] + dp[i - 1][0]) % CEIL;
  29.             dp[i][2] = (dp[i][2] + dp[i - 1][1]) % CEIL;
  31.             dp[i][4] = (dp[i][4] + dp[i - 1][3]) % CEIL;
  32.             dp[i][5] = (dp[i][5] + dp[i - 1][4]) % CEIL;
  33.         }
  34.         long long count = 0;
  35.         for (int i = 0; i < 6; ++i) {
  36.             count = (count + dp[n - 1][i]) % CEIL;
  37.         }
  38.         return count;
  39.     }
  40. };

优化空间复杂度

  1. class Solution {
  2. private:
  3.     static constexpr int CEIL = 1000000007;
  4. public:
  5.     int checkRecord(int n) {
  6.         vector<long long> dp1(6, 0), dp2(6, 0);
  8.         dp1[0] = 1; // 第一天为P
  9.         dp1[1] = 1; // 第一天为L
  10.         dp1[3] = 1; // 第一天为A
  11.         for (int i = 1; i < n; ++i) {
  12.             // 第i天为P
  13.             for (int j = 0; j < 3; ++j) {
  14.                 dp2[0] = (dp2[0] + dp1[j]) % CEIL;
  15.             }
  16.             for (int j = 3; j < 6; ++j) {
  17.                 dp2[3] = (dp2[3] + dp1[j]) % CEIL;
  18.             }
  20.             // 第i天为A
  21.             for (int j = 0; j < 3; ++j) {
  22.                 dp2[3] = (dp2[3] + dp1[j]) % CEIL;
  23.             }
  25.             // 第i天为L
  26.             dp2[1] = (dp2[1] + dp1[0]) % CEIL;
  27.             dp2[2] = (dp2[2] + dp1[1]) % CEIL;
  29.             dp2[4] = (dp2[4] + dp1[3]) % CEIL;
  30.             dp2[5] = (dp2[5] + dp1[4]) % CEIL;
  32.             dp1.swap(dp2);
  33.             fill(dp2.begin(), dp2.end(), 0);
  34.         }
  35.         long long count = 0;
  36.         for (int i = 0; i < 6; ++i) {
  37.             count = (count + dp1[i]) % CEIL;
  38.         }
  39.         return count;
  40.     }
  41. };

优化后时间复杂度为
552. 学生出勤记录 II 2021-08-18 - 图1
空间复杂度为
552. 学生出勤记录 II 2021-08-18 - 图2