Dynamic Programming
Prefix Sum
Description
You are given 3 positive integers zero
, one
, and limit
.
A binary array arr
is called stable if:
The number of occurrences of 0 in arr
is exactly zero
.
The number of occurrences of 1 in arr
is exactly one
.
Each subarray of arr
with a size greater than limit
must contain both 0 and 1.
Return the total number of stable binary arrays.
Since the answer may be very large, return it modulo 109 + 7
.
Example 1:
Input: zero = 1, one = 1, limit = 2
Output: 2
Explanation:
The two possible stable binary arrays are [1,0]
and [0,1]
, as both arrays have a single 0 and a single 1, and no subarray has a length greater than 2.
Example 2:
Input: zero = 1, one = 2, limit = 1
Output: 1
Explanation:
The only possible stable binary array is [1,0,1]
.
Note that the binary arrays [1,1,0]
and [0,1,1]
have subarrays of length 2 with identical elements, hence, they are not stable.
Example 3:
Input: zero = 3, one = 3, limit = 2
Output: 14
Explanation:
All the possible stable binary arrays are [0,0,1,0,1,1]
, [0,0,1,1,0,1]
, [0,1,0,0,1,1]
, [0,1,0,1,0,1]
, [0,1,0,1,1,0]
, [0,1,1,0,0,1]
, [0,1,1,0,1,0]
, [1,0,0,1,0,1]
, [1,0,0,1,1,0]
, [1,0,1,0,0,1]
, [1,0,1,0,1,0]
, [1,0,1,1,0,0]
, [1,1,0,0,1,0]
, and [1,1,0,1,0,0]
.
Constraints:
1 <= zero, one, limit <= 200
Solutions
Solution 1: Memoization Search
We design a function $dfs(i, j, k)$ to represent the number of stable binary arrays that satisfy the problem conditions when there are $i$ $0$s and $j$ $1$s left, and the next number to be filled is $k$. The answer is $dfs(zero, one, 0) + dfs(zero, one, 1)$.
The calculation process of the function $dfs(i, j, k)$ is as follows:
If $i < 0$ or $j < 0$, return $0$.
If $i = 0$, return $1$ when $k = 1$ and $j \leq \textit{limit}$, otherwise return $0$.
If $j = 0$, return $1$ when $k = 0$ and $i \leq \textit{limit}$, otherwise return $0$.
If $k = 0$, we consider the case where the previous number is $0$, $dfs(i - 1, j, 0)$, and the case where the previous number is $1$, $dfs(i - 1, j, 1)$. If the previous number is $0$, it may cause more than $\textit{limit}$ $0$s in the subarray, i.e., the situation where the $\textit{limit} + 1$
Python3 Java C++ Go TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 class Solution :
def numberOfStableArrays ( self , zero : int , one : int , limit : int ) -> int :
@cache
def dfs ( i : int , j : int , k : int ) -> int :
if i == 0 :
return int ( k == 1 and j <= limit )
if j == 0 :
return int ( k == 0 and i <= limit )
if k == 0 :
return (
dfs ( i - 1 , j , 0 )
+ dfs ( i - 1 , j , 1 )
- ( 0 if i - limit - 1 < 0 else dfs ( i - limit - 1 , j , 1 ))
)
return (
dfs ( i , j - 1 , 0 )
+ dfs ( i , j - 1 , 1 )
- ( 0 if j - limit - 1 < 0 else dfs ( i , j - limit - 1 , 0 ))
)
mod = 10 ** 9 + 7
ans = ( dfs ( zero , one , 0 ) + dfs ( zero , one , 1 )) % mod
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
29
30
31
32 class Solution {
private final int mod = ( int ) 1e9 + 7 ;
private Long [][][] f ;
private int limit ;
public int numberOfStableArrays ( int zero , int one , int limit ) {
f = new Long [ zero + 1 ][ one + 1 ][ 2 ] ;
this . limit = limit ;
return ( int ) (( dfs ( zero , one , 0 ) + dfs ( zero , one , 1 )) % mod );
}
private long dfs ( int i , int j , int k ) {
if ( i < 0 || j < 0 ) {
return 0 ;
}
if ( i == 0 ) {
return k == 1 && j <= limit ? 1 : 0 ;
}
if ( j == 0 ) {
return k == 0 && i <= limit ? 1 : 0 ;
}
if ( f [ i ][ j ][ k ] != null ) {
return f [ i ][ j ][ k ] ;
}
if ( k == 0 ) {
f [ i ][ j ][ k ] = ( dfs ( i - 1 , j , 0 ) + dfs ( i - 1 , j , 1 ) - dfs ( i - limit - 1 , j , 1 ) + mod ) % mod ;
} else {
f [ i ][ j ][ k ] = ( dfs ( i , j - 1 , 0 ) + dfs ( i , j - 1 , 1 ) - dfs ( i , j - limit - 1 , 0 ) + mod ) % mod ;
}
return f [ i ][ j ][ k ] ;
}
}
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 class Solution {
public :
int numberOfStableArrays ( int zero , int one , int limit ) {
const int mod = 1e9 + 7 ;
using ll = long long ;
vector < vector < array < ll , 2 >>> f = vector < vector < array < ll , 2 >>> ( zero + 1 , vector < array < ll , 2 >> ( one + 1 , { -1 , -1 }));
auto dfs = [ & ]( auto && dfs , int i , int j , int k ) -> ll {
if ( i < 0 || j < 0 ) {
return 0 ;
}
if ( i == 0 ) {
return k == 1 && j <= limit ;
}
if ( j == 0 ) {
return k == 0 && i <= limit ;
}
ll & res = f [ i ][ j ][ k ];
if ( res != -1 ) {
return res ;
}
if ( k == 0 ) {
res = ( dfs ( dfs , i - 1 , j , 0 ) + dfs ( dfs , i - 1 , j , 1 ) - dfs ( dfs , i - limit - 1 , j , 1 ) + mod ) % mod ;
} else {
res = ( dfs ( dfs , i , j - 1 , 0 ) + dfs ( dfs , i , j - 1 , 1 ) - dfs ( dfs , i , j - limit - 1 , 0 ) + mod ) % mod ;
}
return res ;
};
return ( dfs ( dfs , zero , one , 0 ) + dfs ( dfs , zero , one , 1 )) % mod ;
}
};
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
38
39 func numberOfStableArrays ( zero int , one int , limit int ) int {
const mod int = 1e9 + 7
f := make ([][][ 2 ] int , zero + 1 )
for i := range f {
f [ i ] = make ([][ 2 ] int , one + 1 )
for j := range f [ i ] {
f [ i ][ j ] = [ 2 ] int { - 1 , - 1 }
}
}
var dfs func ( i , j , k int ) int
dfs = func ( i , j , k int ) int {
if i < 0 || j < 0 {
return 0
}
if i == 0 {
if k == 1 && j <= limit {
return 1
}
return 0
}
if j == 0 {
if k == 0 && i <= limit {
return 1
}
return 0
}
res := & f [ i ][ j ][ k ]
if * res != - 1 {
return * res
}
if k == 0 {
* res = ( dfs ( i - 1 , j , 0 ) + dfs ( i - 1 , j , 1 ) - dfs ( i - limit - 1 , j , 1 ) + mod ) % mod
} else {
* res = ( dfs ( i , j - 1 , 0 ) + dfs ( i , j - 1 , 1 ) - dfs ( i , j - limit - 1 , 0 ) + mod ) % mod
}
return * res
}
return ( dfs ( zero , one , 0 ) + dfs ( zero , one , 1 )) % mod
}
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 function numberOfStableArrays ( zero : number , one : number , limit : number ) : number {
const mod = 1e9 + 7 ;
const f : number [][][] = Array . from ({ length : zero + 1 }, () =>
Array . from ({ length : one + 1 }, () => [ - 1 , - 1 ]),
);
const dfs = ( i : number , j : number , k : number ) : number => {
if ( i < 0 || j < 0 ) {
return 0 ;
}
if ( i === 0 ) {
return k === 1 && j <= limit ? 1 : 0 ;
}
if ( j === 0 ) {
return k === 0 && i <= limit ? 1 : 0 ;
}
let res = f [ i ][ j ][ k ];
if ( res !== - 1 ) {
return res ;
}
if ( k === 0 ) {
res = ( dfs ( i - 1 , j , 0 ) + dfs ( i - 1 , j , 1 ) - dfs ( i - limit - 1 , j , 1 ) + mod ) % mod ;
} else {
res = ( dfs ( i , j - 1 , 0 ) + dfs ( i , j - 1 , 1 ) - dfs ( i , j - limit - 1 , 0 ) + mod ) % mod ;
}
return ( f [ i ][ j ][ k ] = res );
};
return ( dfs ( zero , one , 0 ) + dfs ( zero , one , 1 )) % mod ;
}
Solution 2: Dynamic Programming
We can also convert the memoization search of Solution 1 into dynamic programming.
We define $f[i][j][k]$ as the number of stable binary arrays using $i$ $0$s and $j$ $1$s, and the last number is $k$. So the answer is $f[zero][one][0] + f[zero][one][1]$.
Initially, we have $f[i][0][0] = 1$, where $1 \leq i \leq \min(\textit{limit}, \textit{zero})$; and $f[0][j][1] = 1$, where $1 \leq j \leq \min(\textit{limit}, \textit{one})$.
The state transition equation is as follows:
$f[i][j][0] = f[i - 1][j][0] + f[i - 1][j][1] - f[i - \textit{limit} - 1][j][1]$.
$f[i][j][1] = f[i][j - 1][0] + f[i][j - 1][1] - f[i][j - \textit{limit} - 1][0]$.
The time complexity is $O(zero \times one)$, and the space complexity is $O(zero \times one)$.
Python3 Java C++ Go TypeScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 class Solution :
def numberOfStableArrays ( self , zero : int , one : int , limit : int ) -> int :
mod = 10 ** 9 + 7
f = [[[ 0 , 0 ] for _ in range ( one + 1 )] for _ in range ( zero + 1 )]
for i in range ( 1 , min ( limit , zero ) + 1 ):
f [ i ][ 0 ][ 0 ] = 1
for j in range ( 1 , min ( limit , one ) + 1 ):
f [ 0 ][ j ][ 1 ] = 1
for i in range ( 1 , zero + 1 ):
for j in range ( 1 , one + 1 ):
x = 0 if i - limit - 1 < 0 else f [ i - limit - 1 ][ j ][ 1 ]
y = 0 if j - limit - 1 < 0 else f [ i ][ j - limit - 1 ][ 0 ]
f [ i ][ j ][ 0 ] = ( f [ i - 1 ][ j ][ 0 ] + f [ i - 1 ][ j ][ 1 ] - x ) % mod
f [ i ][ j ][ 1 ] = ( f [ i ][ j - 1 ][ 0 ] + f [ i ][ j - 1 ][ 1 ] - y ) % mod
return sum ( f [ zero ][ one ]) % mod
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 class Solution {
public int numberOfStableArrays ( int zero , int one , int limit ) {
final int mod = ( int ) 1e9 + 7 ;
long [][][] f = new long [ zero + 1 ][ one + 1 ][ 2 ] ;
for ( int i = 1 ; i <= Math . min ( zero , limit ); ++ i ) {
f [ i ][ 0 ][ 0 ] = 1 ;
}
for ( int j = 1 ; j <= Math . min ( one , limit ); ++ j ) {
f [ 0 ][ j ][ 1 ] = 1 ;
}
for ( int i = 1 ; i <= zero ; ++ i ) {
for ( int j = 1 ; j <= one ; ++ j ) {
long x = i - limit - 1 < 0 ? 0 : f [ i - limit - 1 ][ j ][ 1 ] ;
long y = j - limit - 1 < 0 ? 0 : f [ i ][ j - limit - 1 ][ 0 ] ;
f [ i ][ j ][ 0 ] = ( f [ i - 1 ][ j ][ 0 ] + f [ i - 1 ][ j ][ 1 ] - x + mod ) % mod ;
f [ i ][ j ][ 1 ] = ( f [ i ][ j - 1 ][ 0 ] + f [ i ][ j - 1 ][ 1 ] - y + mod ) % mod ;
}
}
return ( int ) (( f [ zero ][ one ][ 0 ] + f [ zero ][ one ][ 1 ] ) % mod );
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 class Solution {
public :
int numberOfStableArrays ( int zero , int one , int limit ) {
const int mod = 1e9 + 7 ;
using ll = long long ;
ll f [ zero + 1 ][ one + 1 ][ 2 ];
memset ( f , 0 , sizeof ( f ));
for ( int i = 1 ; i <= min ( zero , limit ); ++ i ) {
f [ i ][ 0 ][ 0 ] = 1 ;
}
for ( int j = 1 ; j <= min ( one , limit ); ++ j ) {
f [ 0 ][ j ][ 1 ] = 1 ;
}
for ( int i = 1 ; i <= zero ; ++ i ) {
for ( int j = 1 ; j <= one ; ++ j ) {
ll x = i - limit - 1 < 0 ? 0 : f [ i - limit - 1 ][ j ][ 1 ];
ll y = j - limit - 1 < 0 ? 0 : f [ i ][ j - limit - 1 ][ 0 ];
f [ i ][ j ][ 0 ] = ( f [ i - 1 ][ j ][ 0 ] + f [ i - 1 ][ j ][ 1 ] - x + mod ) % mod ;
f [ i ][ j ][ 1 ] = ( f [ i ][ j - 1 ][ 0 ] + f [ i ][ j - 1 ][ 1 ] - y + mod ) % mod ;
}
}
return ( f [ zero ][ one ][ 0 ] + f [ zero ][ one ][ 1 ]) % mod ;
}
};
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 func numberOfStableArrays ( zero int , one int , limit int ) int {
const mod int = 1e9 + 7
f := make ([][][ 2 ] int , zero + 1 )
for i := range f {
f [ i ] = make ([][ 2 ] int , one + 1 )
}
for i := 1 ; i <= min ( zero , limit ); i ++ {
f [ i ][ 0 ][ 0 ] = 1
}
for j := 1 ; j <= min ( one , limit ); j ++ {
f [ 0 ][ j ][ 1 ] = 1
}
for i := 1 ; i <= zero ; i ++ {
for j := 1 ; j <= one ; j ++ {
f [ i ][ j ][ 0 ] = ( f [ i - 1 ][ j ][ 0 ] + f [ i - 1 ][ j ][ 1 ]) % mod
if i - limit - 1 >= 0 {
f [ i ][ j ][ 0 ] = ( f [ i ][ j ][ 0 ] - f [ i - limit - 1 ][ j ][ 1 ] + mod ) % mod
}
f [ i ][ j ][ 1 ] = ( f [ i ][ j - 1 ][ 0 ] + f [ i ][ j - 1 ][ 1 ]) % mod
if j - limit - 1 >= 0 {
f [ i ][ j ][ 1 ] = ( f [ i ][ j ][ 1 ] - f [ i ][ j - limit - 1 ][ 0 ] + mod ) % mod
}
}
}
return ( f [ zero ][ one ][ 0 ] + f [ zero ][ one ][ 1 ]) % mod
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24 function numberOfStableArrays ( zero : number , one : number , limit : number ) : number {
const mod = 1e9 + 7 ;
const f : number [][][] = Array . from ({ length : zero + 1 }, () =>
Array . from ({ length : one + 1 }, () => [ 0 , 0 ]),
);
for ( let i = 1 ; i <= Math . min ( limit , zero ); i ++ ) {
f [ i ][ 0 ][ 0 ] = 1 ;
}
for ( let j = 1 ; j <= Math . min ( limit , one ); j ++ ) {
f [ 0 ][ j ][ 1 ] = 1 ;
}
for ( let i = 1 ; i <= zero ; i ++ ) {
for ( let j = 1 ; j <= one ; j ++ ) {
const x = i - limit - 1 < 0 ? 0 : f [ i - limit - 1 ][ j ][ 1 ];
const y = j - limit - 1 < 0 ? 0 : f [ i ][ j - limit - 1 ][ 0 ];
f [ i ][ j ][ 0 ] = ( f [ i - 1 ][ j ][ 0 ] + f [ i - 1 ][ j ][ 1 ] - x + mod ) % mod ;
f [ i ][ j ][ 1 ] = ( f [ i ][ j - 1 ][ 0 ] + f [ i ][ j - 1 ][ 1 ] - y + mod ) % mod ;
}
}
return ( f [ zero ][ one ][ 0 ] + f [ zero ][ one ][ 1 ]) % mod ;
}
GitHub