Sponsored
Sponsored
This approach leverages dynamic programming to count eligible attendance records. We define a function dp[i][a][l], which represents the number of valid sequences of length i with a absences and l consecutive lates. The transitions will account for adding 'P', 'A', or 'L' to existing records, ensuring we respect the problem's constraints.
Time complexity: O(n), Space complexity: O(1), as we use only a fixed amount of space irrespective of n.
1public class AttendanceRecord {
2 public int checkRecord(int n) {
3 final int MOD = 1000000007;
4 int[][][] dp = new int[2][n][3];
5 dp[0][0][0] = 1;
6 for (int i = 0; i < n - 1; i++) {
7 for (int a = 0; a <= 1; a++) {
8 for (int l = 0; l < 3; l++) {
9 dp[a][i + 1][0] = (dp[a][i + 1][0] + dp[a][i][l]) % MOD;
10 if (a == 0) {
11 dp[1][i + 1][0] = (dp[1][i + 1][0] + dp[a][i][l]) % MOD;
12 }
13 if (l < 2) {
14 dp[a][i + 1][l + 1] = (dp[a][i + 1][l + 1] + dp[a][i][l]) % MOD;
15 }
16 }
17 }
18 }
19 int total = 0;
20 for (int a = 0; a <= 1; a++) {
21 for (int l = 0; l < 3; l++) {
22 total = (total + dp[a][n - 1][l]) % MOD;
23 }
24 }
25 return total;
26 }
27
28 public static void main(String[] args) {
29 AttendanceRecord ar = new AttendanceRecord();
30 int n = 2;
31 System.out.println(ar.checkRecord(n));
32 }
33}The Java solution implements a 3D dynamic programming array similar to the C++ solution, effectively iterating through possible character additions while respecting the problem's restrictions.
This approach uses matrix exponentiation to efficiently solve the problem by leveraging the recursive relationship of the transformation matrices, which model the state transitions of the sequences. The matrix exponentiation technique drastically reduces the time complexity by harnessing fast exponentiation properties.
Time complexity: O(log n), Space complexity: O(1), because we only manipulate fixed-size arrays.
1
This Python code uses functions for matrix multiplication and exponentiation in order to model the problem's constraints and efficiently calculate the total valid sequences.