题目描述
原题链接： LeetCode.552 学生出勤记录II
解题思路
-
根据题意， 缺勤天数最多只有一天， 迟到最多只能连续两天， 可以按末尾两个字符状态作为DP数组含义的不同维度往后递推长度增长时的数量值。 dp[i][j]中的i表示长度为i的出勤记录， j表示末尾字符状态：
j的值 含义 0 无缺勤且最后不以'L'结尾 1 无缺勤且最后一位是'L'， 倒数第二位不是'L' 2 无缺勤且最后两位是'L' 3 有一天缺勤且最后不以'L'结尾 4 有一天缺勤且最后一位是'L'， 倒数第二位不是'L‘ 5 有一天缺勤且最后两位是'L' -
长度为1的对应初始值为{1, 1, 0, 1, 0, 0}；
-
可以由长度i递推出长度i+1各状态出勤记录的数量：
j的值 i相关递推公式 递推理由 0 \(dp_i0+dp_i1+dp_i2\) 前i位没有缺勤记录的三种情况再追加1个'P'都能得到\(dp_{i+1}0\)对应状态 1 \(dp_i0\) 第i+1位确定是'L'且第i位不能是'L'， 同时无缺勤记录， 只能是由\(dp_i0\)追加1个'L'得到 2 \(dp_i1\) 第i+1位确定是'L'且第i位也是'L'， 同时无缺勤记录， 只能是由\(dp_i1\)追加1个'L'得到 3 \(dp_i0+dp_i1+dp_i2+dp_i3+dp_i4+dp_i5\) 前i位没有缺勤记录的三种情况再追加1个'A'， 或者前i位有1天缺勤再追加1个'P' 4 \(dp_i3\) 前i位有1天缺勤记录但是第i位不能是'L'， 只有这种情况追加1个'L'能得到\(dp_{i+1}4\)的状态 5 \(dp_i4\) 前i位有1天缺勤记录且第i位是'L'， 只有这种情况追加1个'L'能得到\(dp_{i+1}5\)的状态 -
确定递推公式后可以进一步确定递推矩阵， 借助矩阵快速幂技巧求得时间复杂度最优解：
-
设长度为i的出勤记录6种状态的数量值矩阵为\(A_i=\begin{pmatrix}dp_i0&dp_i1&dp_i2&dp_i3&dp_i4&dp_i5\end{pmatrix}\)， 存在矩阵B使得 \(A_i * B = A_{i+1}\)成立；
-
长度为i的出勤记录6种状态的数量值就可以通过\(A_1*B^{i-1}\)计算得到， 也就是通过求递推矩阵B的幂来得到；
-
由递推公式中各项前置变量的常数是1或0来快速确认递推矩阵中的每列， 具体见下表：
递推公式 递推矩阵的列 \(dp_{i+1}0=dp_i0+dp_i1+dp_i2\) \(\begin{pmatrix}1\\1\\1\\0\\0\\0\end{pmatrix}\) \(dp_{i+1}1=dp_i0\) \(\begin{pmatrix}1\\0\\0\\0\\0\\0\end{pmatrix}\) \(dp_{i+1}2=dp_i1\) \(\begin{pmatrix}0\\1\\0\\0\\0\\0\end{pmatrix}\) \(dp_{i+1}3=dp_i0+dp_i1+dp_i2+dp_i3+dp_i4+dp_i5\) \(\begin{pmatrix}1\\1\\1\\1\\1\\1\end{pmatrix}\) \(dp_{i+1}4=dp_i3\) \(\begin{pmatrix}0\\0\\0\\1\\0\\0\end{pmatrix}\) \(dp_{i+1}5=dp_i4\) \(\begin{pmatrix}0\\0\\0\\0\\1\\0\end{pmatrix}\)
-
-
本题难点就在于明确DP数组含义以及递推公式的确定， 后续无论是用正常动态规划或者矩阵快速幂都能快速写出对应代码；
-
普通动态规划的时间复杂度是\(O(n)\)， 矩阵快速幂能优化到\(6^3 * log_2n\)。
解题代码
-
6维动态规划版本
final int MOD = 1_000_000_007; /** * 第一版代码基础上优化用一维数组滚动DP * 执行用时： 24 ms , 在所有 Java 提交中击败了 79.83% 的用户 * 内存消耗： 43.20 MB , 在所有 Java 提交中击败了 75.63% 的用户 */ public int checkRecord(int n) { /* * 按照题意, 出勤记录中'A'的数量最多就1个, 迟到的'L'不会连续出现超过3个 * dp[i][0]: 长度为i的出勤记录中没有缺勤且结尾不为'L', dp[i-1][0] + dp[i-1][1] + dp[i-1][2] * dp[i][1]: 长度为i的出勤记录中没有缺勤且结尾为1个'L', dp[i-1][0] * dp[i][2]: 长度为i的出勤记录中没有缺勤且结尾为2个'L', dp[i-1][1] * dp[i][3]: 长度为i的出勤记录中有1个缺勤且结尾不为'L', dp[i-1][0~5] * dp[i][4]: 长度为i的出勤记录中有1个缺勤且结尾为1个'L', dp[i-1][3] * dp[i][5]: 长度为i的出勤记录中有1个缺勤且结尾为2个'L', dp[i-1][4] */ int[] dp = new int[6]; dp[0] = 1; dp[1] = 1; dp[2] = 0; dp[3] = 1; dp[4] = 0; dp[5] = 0; for (int i = 2; i <= n; i++) { int[] next = new int[6]; next[0] = (int) (((long) dp[0] + dp[1] + dp[2]) % MOD); next[1] = dp[0]; next[2] = dp[1]; next[3] = (int) (((long) next[0] + dp[3] + dp[4] + dp[5]) % MOD); next[4] = dp[3]; next[5] = dp[4]; dp = next; } int res = 0; for (int i = 0; i < 6; i++) { res = (res + dp[i]) % MOD; } return res; } -
矩阵快速幂版本
final int MOD = 1_000_000_007; /** * 矩阵快速幂解法 * 执行用时： 2 ms , 在所有 Java 提交中击败了 100.00% 的用户 * 内存消耗： 39.86 MB , 在所有 Java 提交中击败了 79.51% 的用户 */ public int checkRecord(int n) { int[][] start = {{1, 1, 0, 1, 0, 0}}; int[][] transfer = { {1, 1, 0, 1, 0, 0}, {1, 0, 1, 1, 0, 0}, {1, 0, 0, 1, 0, 0}, {0, 0, 0, 1, 1, 0}, {0, 0, 0, 1, 0, 1}, {0, 0, 0, 1, 0, 0}}; int[][] res = multiply(start, power(transfer, n - 1, MOD), MOD); int ans = 0; for (int a : res[0]) { ans = (ans + a) % MOD; } return ans; } /** * 矩阵求幂并对mod取余 */ public int[][] power(int[][] base, int n, int mod) { int row = base.length; int[][] res = new int[row][row]; for (int i = 0; i < row; i++) { res[i][i] = 1; } while (n > 0) { if ((n & 1) == 1) { res = multiply(res, base, mod); } base = multiply(base, base, mod); n >>= 1; } return res; } /** * 矩阵相乘并对mod取余 */ public int[][] multiply(int[][] a, int[][] b, int mod) { int m = a.length, n = b[0].length; int[][] res = new int[m][n]; int k = b.length; for (int aRow = 0; aRow < m; aRow++) { for (int bCol = 0; bCol < n; bCol++) { long sum = 0; for (int i = 0; i < k; i++) { sum = (sum + (long) a[aRow][i] * b[i][bCol]) % mod; } res[aRow][bCol] = (int) sum; } } return res; }
标签：出勤,记录,int,552,II,缺勤,pmatrix,LeetCode,dp From： https://www.cnblogs.com/coding-memory/p/18091556参考链接：
左程云大佬的B站算法讲解视频01:53:30开始