You are given 3 positive integers zero, one, and limit.
A binary arrayarr is called stable if:
The number of occurrences of 0 in arr is exactly zero.
The number of occurrences of 1 in arr is exactlyone.
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 modulo109 + 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].
Example 2:
Input:zero = 1, one = 2, limit = 1
Output:1
Explanation:
The only possible stable binary array is [1,0,1].
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 <= 1000
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 \text{limit}$, otherwise return $0$.
If $j = 0$, return $1$ when $k = 0$ and $i \leq \text{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 $\text{limit}$ $0$s in the subarray, i.e., the situation where the $\text{limit} + 1$
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(\text{limit}, \text{zero})$; and $f[0][j][1] = 1$, where $1 \leq j \leq \min(\text{limit}, \text{one})$.