551. Student Attendance Record I + Student Attendance Record II

▶ 一个学生的考勤状况是一个字符串，其中各字符的含义是：A 缺勤，L 迟到，P 正常。如果一个学生考勤状况中 A 不超过一个，且没有连续两个 L（L 可以有多个，但是不能连续），则称该学生达标（原文表述：A student could be rewarded if his attendance record doesn't contain more than one 'A' (absent) or more than two continuous 'L' (late). ）

▶ 551. 给定一个学生的考勤状况，判断他能否达标。

● 代码，4 ms，简单的计数，最快的解法算法与之相同

 1 class Solution
 2 {
 3 public:
 4     bool checkRecord(string s)
 5     {
 6         int i, a, l;
 7         for (i = a = l = 0; i < s.size(); i++)
 8         {
 9             if (s[i] == 'A')
10                 a++;
11             if (s[i] == 'L')
12                 l++;
13             else            // 出现 A 或 P 时均要清空 L 计数
14                 l = 0;
15             if (a >= 2 || l > 2)
16                 return false;
17         }
18         return true;
19     }
20 };

▶ 552. 给定正整数 n，考虑所有长度为 n 的考勤状况（3n 种可能），计算达标的考勤状况数，该数字可能非常大，取关于 109 + 7（竟然是个素数）模作为输出结果

● 自己的代码，29 ms，时间复杂度 O(n)，考虑递推数列，一个达标序列只能是以下三种情况：

a[ k ] 表长度为 k，以 P 结尾，不含 A 的达标序列个数

b[ k ] 表长度为 k，以 PL 结尾，不含 A 的达标序列个数（不能是 LLLP 结尾）

c[ k ] 表长度为 k，以 LL 结尾，不含 A 的达标序列个数（不能是 LLL 结尾）

注意到 a[ 1 ] = b[ 1 ] = 1，c[ 1 ] = 0，a[ k ] = a[ k - 1 ] + b[ k - 1 ] + c[ k - 1]（任意一种达标序列添个 P），b[ k ] = a[ k - 1 ]（P 结尾的达标序列添个 L），c[ k ] = b[ k - 1 ]（PL 结尾的达标序列添个 L）

约化后就变成了 a[ 1 ] = 1，a[ 2 ] = 2，a[ 3 ] = 4，a[ n ] = a[ n - 1 ] + a[ n - 2 ] + a[ n - 3 ]  ( n ≥ 4 )

对上述数列打表，使用长度为 n+1 的表 f，其中 a[ k ] = f[ k - 1 ]，即所有下标有一单位的平移，在代码中注意控制

因为打表序列中 A 至多一个，所以按照 A 的位置分类讨论：

① 不含A，一共有 a[ n ] + b[ n ] + c[ n ] = a[ n + 1 ] 种情况，等于 f[ n ]（打表要长一格的原因）

② A 在开头，一共有 a[ n - 1 ] + b[ n - 1 ] + c[ n - 1 ] = a[ n ] 种情况，等于 f[ n - 1 ]

③ A 在结尾，同上，等于 f[ n - 1 ]

④ A 在中间，考虑 A 的左边有长度为 i 的不含 A 的序列，且 A 的右边有长度为 n - i - 1 的不含A的序列，一共是 ( a[ i ] + b[ i ] + c[ i ] ) * ( a[ n - i - 1 ] + b[ n - i - 1 ] + c[ n - i - 1 ] )，即 f[ i ] * f[ n - i - 1 ]，
i 在 i = 1 到 i = n - 2 之间求和。

注意每一步取模运算，因为 f 本身是指数级增长的。

 1 class Solution
 2 {
 3 public:
 4     int checkRecord(int n)
 5     {
 6         if (n == 1)
 7             return 3;
 8         const int m = 1000000007;
 9         vector<long long> f(n + 1, 0);
10         int i,sum;
11         for (f[0] = 1, f[1] = 2, f[2] = 4, i = 3; i <= n; f[i] = (f[i - 1] + f[i - 2] + f[i - 3]) % m, i++);
12         for (sum = (f[n] + f[n - 1] * 2) % m, i = 1; i < n - 1; i++)
13             sum = (sum + f[i] * f[n - i - 1]) % m;
14         return sum;
15     }
16 };

● 代码，4 ms，使用一个矩阵的幂来计算递推

  1 #define ENTRY(A, i, j)  ((A)[(i) * n + (j)])
  2 
  3 int64_t* NewMatrix(size_t n)
  4 {
  5     assert(n >= 1);
  6     int64_t* temp = (int64_t*)calloc(n * n, sizeof(int64_t));
  7     assert(temp != NULL);
  8     return temp;
  9 }
 10 
 11 void FreeMatrix(int64_t* A)
 12 {
 13     free(A);
 14 }
 15 
 16 void SetMatrix(int64_t* A, int64_t* B, size_t n)
 17 {
 18     memcpy(A, B, n * n * sizeof(int64_t));
 19 }
 20 
 21 void IdentityMatrix(int64_t* A, size_t n)// 将方阵 A 赋值为单位方阵
 22 {
 23     int i, j;
 24     for (i = 0; i < n; i++)
 25     {
 26         for (j = 0; j < n; j++)
 27             ENTRY(A, i, j) = (i == j);
 28     }
 29 }
 30 
 31 void MatrixMultiply(int64_t* A, int64_t* B, size_t n)// 方阵乘法 A = A * B
 32 {
 33     assert(n >= 1);
 34     int64_t* C = NewMatrix(n);
 35     int i, j, k;
 36     for (i = 0; i < n; ++i)
 37     {
 38         for (j = 0; j < n; ++j)
 39         {
 40             ENTRY(C, i, j) = 0;
 41             for (k = 0; k < n; ++k)
 42                 ENTRY(C, i, j) += ENTRY(A, i, k) * ENTRY(B, k, j);            
 43         }
 44     }
 45     memcpy(A, C, n * n * sizeof(int64_t));
 46     FreeMatrix(C);
 47 }
 48 
 49 void MatrixPower(int64_t* C, int64_t* A, size_t n, int m)// 方阵幂 C = A ^ m 
 50 {
 51     assert(n >= 1);
 52     assert(m >= 0);
 53     int64_t* B = NewMatrix(n);
 54     SetMatrix(B, A, n);
 55     IdentityMatrix(C, n);
 56     for (; m > 0; m /= 2)// 二进制方法
 57     {
 58         if (m % 2 == 1)
 59             MatrixMultiply(C, B, n);
 60         MatrixMultiply(B, B, n);        
 61     }
 62     FreeMatrix(B);
 63 }
 64 
 65 void MatrixModulus(int64_t* A, size_t n, int64_t modulus)// 方阵逐格求模 A %= m
 66 {
 67     int i, j;
 68     for (i = 0; i < n; ++i)
 69     {
 70         for (j = 0; j < n; ++j)
 71             ENTRY(A, i, j) = ENTRY(A, i, j) % modulus;
 72     }
 73 }
 74 
 75 void MatrixModulusPower(int64_t* C, int64_t* A, size_t n, int m, int64_t modulus)// C = A ^ m % modulus
 76 {
 77     assert(n >= 1);
 78     assert(m >= 0);
 79     int64_t* B = NewMatrix(n);
 80     SetMatrix(B, A, n);
 81     IdentityMatrix(C, n);
 82     for (; m > 0;m/=2)
 83     {
 84         if (m % 2 == 1)
 85         {
 86             MatrixMultiply(C, B, n);
 87             MatrixModulus(C, n, modulus);
 88         }
 89         MatrixMultiply(B, B, n);
 90         MatrixModulus(B, n, modulus);        
 91     }
 92     FreeMatrix(B);
 93 }
 94 
 95 int AttendanceNumber(int m)
 96 {
 97     assert(m >= 0);
 98     size_t n = 6;
 99     int64_t initial_vector[6] = { 1, 3, 8, 19, 43, 94 };
100     int64_t modulus = 1000000007;
101     int64_t* A = NewMatrix(n);
102     ENTRY(A, 0, 1) = 1;
103     ENTRY(A, 1, 2) = 1;
104     ENTRY(A, 2, 3) = 1;
105     ENTRY(A, 3, 4) = 1;
106     ENTRY(A, 4, 5) = 1;
107     ENTRY(A, 5, 0) = -1;
108     ENTRY(A, 5, 1) = -2;
109     ENTRY(A, 5, 2) = -3;
110     ENTRY(A, 5, 3) = 0;
111     ENTRY(A, 5, 4) = 1;
112     ENTRY(A, 5, 5) = 2;
113     int64_t answer = 0;
114     if (m <= 5)
115         answer = initial_vector[m];
116     else
117     {
118         int64_t* C = NewMatrix(n);
119         MatrixModulusPower(C, A, n, m - n + 1, modulus);
120         for (size_t i = 0; i < n; ++i)
121             answer += ENTRY(C, n - 1, i) * initial_vector[i];
122         answer = (answer % modulus + modulus) % modulus;
123         FreeMatrix(C);
124     }
125     FreeMatrix(A);
126     return answer;
127 }
128 
129 #undef ENTRY
130 
131 class Solution
132 {
133 public:
134     int checkRecord(int n)
135     {
136         return AttendanceNumber(n);
137     }
138 };

● 初版动态规划（MLE），f[ i ][ j ][ k ] 表示长度为 i，至多 j 个 A，至多 k 个连续 L 的序列。所求目标为 f[ n ][ 1 ][ 2 ]，转移方程如下，发现可以用矩阵幂来一次性计算 f[ n ]

　　

 1 class Solution
 2 {
 3 public:
 4     int checkRecord(int n)
 5     {
 6         const int MOD = 1000000007;
 7         vector<vector<vector<int>>> f(n + 1, vector<vector<int>>(2, vector<int>(3, 0)));
 8         int i, j, k, val;
 9         for (i = 0; i < 2; i++)
10             for (j = 0; j < 3; f[0][i][j++] = 1);        
11         for (i = 1; i <= n; i++)
12         {
13             for (j = 0; j < 2; j++)
14             {
15                 for (k = 0; k < 3; k++)
16                 {
17                     val = f[i - 1][j][2];                       // P
18                     if (j > 0)                                  // A
19                         val = (val + f[i - 1][j - 1][2]) % MOD;  
20                     if (k > 0)                                  // L
21                         val = (val + f[i - 1][j][k - 1]) % MOD;  
22                     f[i][j][k] = val;
23                 }
24             }
25         }
26         return f[n][1][2];
27     }
28 };

● 改进动态规划，8 ms，直接用矩阵幂来计算

 1 class Solution
 2 {
 3 public:
 4     const int MOD = 1000000007, M = 6;
 5     void mul(vector<vector<int>>& A, vector<vector<int>>& B)
 6     {
 7         vector<vector<int>> temp(M, vector<int>(M, 0));
 8         int i, j, k;
 9         for (i = 0; i < M; i++)
10         {
11             for (j = 0; j < M; j++)
12             {
13                 for (k = 0; k < M; k++)
14                     temp[i][j] = (int)((temp[i][j] + (long)A[i][k] * B[k][j]) % MOD);
15             }
16         }
17         A = temp;
18         return;
19     }
20     void pow(vector<vector<int>>& A, int n)
21     {
22         vector<vector<int>> temp(M, vector<int>(M, 0));
23         for (int i = 0; i < M; temp[i][i] = 1, i++);
24         for (; n > 0; n /= 2)
25         {
26             if (n % 2)
27                 mul(temp, A);
28             mul(A, A);
29         }
30         A = temp;
31         return;
32     }
33     int checkRecord(int n)
34     {
35         vector<vector<int>> A = 
36         {
37             { 0, 0, 1, 0, 0, 0 },
38             { 1, 0, 1, 0, 0, 0 },
39             { 0, 1, 1, 0, 0, 0 },
40             { 0, 0, 1, 0, 0, 1 },
41             { 0, 0, 1, 1, 0, 1 },
42             { 0, 0, 1, 0, 1, 1 },
43         };
44         pow(A, n + 1);
45         return A[5][2];
46     }
47 };

● 代码，深度优先遍历，TLE，说明穷举肯定不行

 1 class Solution
 2 {
 3 public:
 4     int checkRecord(int n)
 5     {
 6         long long res = 0;
 7         dfs(n, 0, 0, 0, res);
 8         return res % 1000000007;
 9     }
10     void dfs(int n, int s, int A, int L, long long& res)// 当前共 s 位，有 A 个 A 和 L 个 L
11     {
12         if (s == n)
13         {
14             res++;
15             return;
16         }
17         dfs(n, s + 1, A, 0, res);   //add "P"
18         if (A < 1)
19             dfs(n, s + 1, A + 1, 0, res);
20         if (L <= 1)
21             dfs(n, s + 1, A, L + 1, res);
22     }
23 };
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/cuancuancuanhao/p/8387655.html