Dynamic Programming
Description
An attendance record for a student can be represented as a string where each character signifies whether the student was absent, late, or present on that day. The record only contains the following three characters:
'A'
: Absent.
'L'
: Late.
'P'
: Present.
Any student is eligible for an attendance award if they meet both of the following criteria:
The student was absent ('A'
) for strictly fewer than 2 days total .
The student was never late ('L'
) for 3 or more consecutive days.
Given an integer n
, return the number of possible attendance records of length n
that make a student eligible for an attendance award. The answer may be very large, so return it modulo 109 + 7
.
Example 1:
Input: n = 2
Output: 8
Explanation: There are 8 records with length 2 that are eligible for an award:
"PP", "AP", "PA", "LP", "PL", "AL", "LA", "LL"
Only "AA" is not eligible because there are 2 absences (there need to be fewer than 2).
Example 2:
Input: n = 1
Output: 3
Example 3:
Input: n = 10101
Output: 183236316
Constraints:
Solutions
Solution 1
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 class Solution :
def checkRecord ( self , n : int ) -> int :
@cache
def dfs ( i , j , k ):
if i >= n :
return 1
ans = 0
if j == 0 :
ans += dfs ( i + 1 , j + 1 , 0 )
if k < 2 :
ans += dfs ( i + 1 , j , k + 1 )
ans += dfs ( i + 1 , j , 0 )
return ans % mod
mod = 10 ** 9 + 7
ans = dfs ( 0 , 0 , 0 )
dfs . cache_clear ()
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 class Solution {
private final int mod = ( int ) 1e9 + 7 ;
private int n ;
private Integer [][][] f ;
public int checkRecord ( int n ) {
this . n = n ;
f = new Integer [ n ][ 2 ][ 3 ] ;
return dfs ( 0 , 0 , 0 );
}
private int dfs ( int i , int j , int k ) {
if ( i >= n ) {
return 1 ;
}
if ( f [ i ][ j ][ k ] != null ) {
return f [ i ][ j ][ k ] ;
}
int ans = dfs ( i + 1 , j , 0 );
if ( j == 0 ) {
ans = ( ans + dfs ( i + 1 , j + 1 , 0 )) % mod ;
}
if ( k < 2 ) {
ans = ( ans + dfs ( i + 1 , j , k + 1 )) % mod ;
}
return f [ i ][ j ][ k ] = ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25 class Solution {
public :
int checkRecord ( int n ) {
int f [ n ][ 2 ][ 3 ];
memset ( f , -1 , sizeof ( f ));
const int mod = 1e9 + 7 ;
auto dfs = [ & ]( auto && dfs , int i , int j , int k ) -> int {
if ( i >= n ) {
return 1 ;
}
if ( f [ i ][ j ][ k ] != -1 ) {
return f [ i ][ j ][ k ];
}
int ans = dfs ( dfs , i + 1 , j , 0 );
if ( j == 0 ) {
ans = ( ans + dfs ( dfs , i + 1 , j + 1 , 0 )) % mod ;
}
if ( k < 2 ) {
ans = ( ans + dfs ( dfs , i + 1 , j , k + 1 )) % mod ;
}
return f [ i ][ j ][ k ] = ans ;
};
return dfs ( dfs , 0 , 0 , 0 );
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32 func checkRecord ( n int ) int {
f := make ([][][] int , n )
for i := range f {
f [ i ] = make ([][] int , 2 )
for j := range f [ i ] {
f [ i ][ j ] = make ([] int , 3 )
for k := range f [ i ][ j ] {
f [ i ][ j ][ k ] = - 1
}
}
}
const mod = 1e9 + 7
var dfs func ( i , j , k int ) int
dfs = func ( i , j , k int ) int {
if i >= n {
return 1
}
if f [ i ][ j ][ k ] != - 1 {
return f [ i ][ j ][ k ]
}
ans := dfs ( i + 1 , j , 0 )
if j == 0 {
ans = ( ans + dfs ( i + 1 , j + 1 , 0 )) % mod
}
if k < 2 {
ans = ( ans + dfs ( i + 1 , j , k + 1 )) % mod
}
f [ i ][ j ][ k ] = ans
return ans
}
return dfs ( 0 , 0 , 0 )
}
Solution 2
Python3 Java C++ Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 class Solution :
def checkRecord ( self , n : int ) -> int :
mod = int ( 1e9 + 7 )
dp = [[[ 0 , 0 , 0 ], [ 0 , 0 , 0 ]] for _ in range ( n )]
# base case
dp [ 0 ][ 0 ][ 0 ] = dp [ 0 ][ 0 ][ 1 ] = dp [ 0 ][ 1 ][ 0 ] = 1
for i in range ( 1 , n ):
# A
dp [ i ][ 1 ][ 0 ] = ( dp [ i - 1 ][ 0 ][ 0 ] + dp [ i - 1 ][ 0 ][ 1 ] + dp [ i - 1 ][ 0 ][ 2 ]) % mod
# L
dp [ i ][ 0 ][ 1 ] = dp [ i - 1 ][ 0 ][ 0 ]
dp [ i ][ 0 ][ 2 ] = dp [ i - 1 ][ 0 ][ 1 ]
dp [ i ][ 1 ][ 1 ] = dp [ i - 1 ][ 1 ][ 0 ]
dp [ i ][ 1 ][ 2 ] = dp [ i - 1 ][ 1 ][ 1 ]
# P
dp [ i ][ 0 ][ 0 ] = ( dp [ i - 1 ][ 0 ][ 0 ] + dp [ i - 1 ][ 0 ][ 1 ] + dp [ i - 1 ][ 0 ][ 2 ]) % mod
dp [ i ][ 1 ][ 0 ] = (
dp [ i ][ 1 ][ 0 ] + dp [ i - 1 ][ 1 ][ 0 ] + dp [ i - 1 ][ 1 ][ 1 ] + dp [ i - 1 ][ 1 ][ 2 ]
) % mod
ans = 0
for j in range ( 2 ):
for k in range ( 3 ):
ans = ( ans + dp [ n - 1 ][ j ][ k ]) % mod
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 class Solution {
private static final int MOD = 1000000007 ;
public int checkRecord ( int n ) {
long [][][] dp = new long [ n ][ 2 ][ 3 ] ;
// base case
dp [ 0 ][ 0 ][ 0 ] = 1 ;
dp [ 0 ][ 0 ][ 1 ] = 1 ;
dp [ 0 ][ 1 ][ 0 ] = 1 ;
for ( int i = 1 ; i < n ; i ++ ) {
// A
dp [ i ][ 1 ][ 0 ] = ( dp [ i - 1 ][ 0 ][ 0 ] + dp [ i - 1 ][ 0 ][ 1 ] + dp [ i - 1 ][ 0 ][ 2 ] ) % MOD ;
// L
dp [ i ][ 0 ][ 1 ] = dp [ i - 1 ][ 0 ][ 0 ] ;
dp [ i ][ 0 ][ 2 ] = dp [ i - 1 ][ 0 ][ 1 ] ;
dp [ i ][ 1 ][ 1 ] = dp [ i - 1 ][ 1 ][ 0 ] ;
dp [ i ][ 1 ][ 2 ] = dp [ i - 1 ][ 1 ][ 1 ] ;
// P
dp [ i ][ 0 ][ 0 ] = ( dp [ i - 1 ][ 0 ][ 0 ] + dp [ i - 1 ][ 0 ][ 1 ] + dp [ i - 1 ][ 0 ][ 2 ] ) % MOD ;
dp [ i ][ 1 ][ 0 ] = ( dp [ i ][ 1 ][ 0 ] + dp [ i - 1 ][ 1 ][ 0 ] + dp [ i - 1 ][ 1 ][ 1 ] + dp [ i - 1 ][ 1 ][ 2 ] ) % MOD ;
}
long ans = 0 ;
for ( int j = 0 ; j < 2 ; j ++ ) {
for ( int k = 0 ; k < 3 ; k ++ ) {
ans = ( ans + dp [ n - 1 ][ j ][ k ] ) % MOD ;
}
}
return ( int ) ans ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33 constexpr int MOD = 1e9 + 7 ;
class Solution {
public :
int checkRecord ( int n ) {
using ll = long long ;
vector < vector < vector < ll >>> dp ( n , vector < vector < ll >> ( 2 , vector < ll > ( 3 )));
// base case
dp [ 0 ][ 0 ][ 0 ] = dp [ 0 ][ 0 ][ 1 ] = dp [ 0 ][ 1 ][ 0 ] = 1 ;
for ( int i = 1 ; i < n ; ++ i ) {
// A
dp [ i ][ 1 ][ 0 ] = ( dp [ i - 1 ][ 0 ][ 0 ] + dp [ i - 1 ][ 0 ][ 1 ] + dp [ i - 1 ][ 0 ][ 2 ]) % MOD ;
// L
dp [ i ][ 0 ][ 1 ] = dp [ i - 1 ][ 0 ][ 0 ];
dp [ i ][ 0 ][ 2 ] = dp [ i - 1 ][ 0 ][ 1 ];
dp [ i ][ 1 ][ 1 ] = dp [ i - 1 ][ 1 ][ 0 ];
dp [ i ][ 1 ][ 2 ] = dp [ i - 1 ][ 1 ][ 1 ];
// P
dp [ i ][ 0 ][ 0 ] = ( dp [ i - 1 ][ 0 ][ 0 ] + dp [ i - 1 ][ 0 ][ 1 ] + dp [ i - 1 ][ 0 ][ 2 ]) % MOD ;
dp [ i ][ 1 ][ 0 ] = ( dp [ i ][ 1 ][ 0 ] + dp [ i - 1 ][ 1 ][ 0 ] + dp [ i - 1 ][ 1 ][ 1 ] + dp [ i - 1 ][ 1 ][ 2 ]) % MOD ;
}
ll ans = 0 ;
for ( int j = 0 ; j < 2 ; ++ j ) {
for ( int k = 0 ; k < 3 ; ++ k ) {
ans = ( ans + dp [ n - 1 ][ j ][ k ]) % MOD ;
}
}
return ans ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37 const _mod int = 1e9 + 7
func checkRecord ( n int ) int {
dp := make ([][][] int , n )
for i := 0 ; i < n ; i ++ {
dp [ i ] = make ([][] int , 2 )
for j := 0 ; j < 2 ; j ++ {
dp [ i ][ j ] = make ([] int , 3 )
}
}
// base case
dp [ 0 ][ 0 ][ 0 ] = 1
dp [ 0 ][ 0 ][ 1 ] = 1
dp [ 0 ][ 1 ][ 0 ] = 1
for i := 1 ; i < n ; i ++ {
// A
dp [ i ][ 1 ][ 0 ] = ( dp [ i - 1 ][ 0 ][ 0 ] + dp [ i - 1 ][ 0 ][ 1 ] + dp [ i - 1 ][ 0 ][ 2 ]) % _mod
// L
dp [ i ][ 0 ][ 1 ] = dp [ i - 1 ][ 0 ][ 0 ]
dp [ i ][ 0 ][ 2 ] = dp [ i - 1 ][ 0 ][ 1 ]
dp [ i ][ 1 ][ 1 ] = dp [ i - 1 ][ 1 ][ 0 ]
dp [ i ][ 1 ][ 2 ] = dp [ i - 1 ][ 1 ][ 1 ]
// P
dp [ i ][ 0 ][ 0 ] = ( dp [ i - 1 ][ 0 ][ 0 ] + dp [ i - 1 ][ 0 ][ 1 ] + dp [ i - 1 ][ 0 ][ 2 ]) % _mod
dp [ i ][ 1 ][ 0 ] = ( dp [ i ][ 1 ][ 0 ] + dp [ i - 1 ][ 1 ][ 0 ] + dp [ i - 1 ][ 1 ][ 1 ] + dp [ i - 1 ][ 1 ][ 2 ]) % _mod
}
var ans int
for j := 0 ; j < 2 ; j ++ {
for k := 0 ; k < 3 ; k ++ {
ans = ( ans + dp [ n - 1 ][ j ][ k ]) % _mod
}
}
return ans
}
GitHub