class Solution {
public:
int numberOfStableArrays(int zero, int one, int limit) {
}
};
3129. 找出所有稳定的二进制数组 I
给你 3 个正整数 zero ，one 和 limit 。
一个 二进制数组 arr 如果满足以下条件，那么我们称它是 稳定的 ：
arr 中出现次数 恰好 为 zero 。arr 中出现次数 恰好 为 one 。arr 中每个长度超过 limit 的 子数组 都 同时 包含 0 和 1 。请你返回 稳定 二进制数组的 总 数目。
由于答案可能很大，将它对 109 + 7 取余 后返回。
示例 1：
输入：zero = 1, one = 1, limit = 2
输出：2
解释：
两个稳定的二进制数组为 [1,0] 和 [0,1] ，两个数组都有一个 0 和一个 1 ，且没有子数组长度大于 2 。
示例 2：
输入：zero = 1, one = 2, limit = 1
输出：1
解释：
唯一稳定的二进制数组是 [1,0,1] 。
二进制数组 [1,1,0] 和 [0,1,1] 都有长度为 2 且元素全都相同的子数组，所以它们不稳定。
示例 3：
输入：zero = 3, one = 3, limit = 2
输出：14
解释：
所有稳定的二进制数组包括 [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] 和 [1,1,0,1,0,0] 。
提示：
1 <= zero, one, limit <= 200原站题解
golang 解法, 执行用时: 7 ms, 内存消耗: 6.8 MB, 提交时间: 2024-05-01 10:52:33
func numberOfStableArrays(zero, one, limit int) (ans int) {
const mod = 1_000_000_007
f := make([][][2]int, zero+1)
for i := range f {
f[i] = make([][2]int, one+1)
}
for i := 1; i <= min(limit, zero); i++ {
f[i][0][0] = 1
}
for j := 1; j <= min(limit, one); 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 {
// + mod 保证答案非负
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 {
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
}
cpp 解法, 执行用时: 11 ms, 内存消耗: 13.6 MB, 提交时间: 2024-05-01 10:52:20
class Solution {
public:
int numberOfStableArrays(int zero, int one, int limit) {
const int MOD = 1'000'000'007;
vector<vector<array<int, 2>>> f(zero + 1, vector<array<int, 2>>(one + 1));
for (int i = 1; i <= min(limit, zero); i++) {
f[i][0][0] = 1;
}
for (int j = 1; j <= min(limit, one); j++) {
f[0][j][1] = 1;
}
for (int i = 1; i <= zero; i++) {
for (int j = 1; j <= one; j++) {
// + MOD 保证答案非负
f[i][j][0] = ((long long) f[i - 1][j][0] + f[i - 1][j][1] + (i > limit ? MOD - f[i - limit - 1][j][1] : 0)) % MOD;
f[i][j][1] = ((long long) f[i][j - 1][0] + f[i][j - 1][1] + (j > limit ? MOD - f[i][j - limit - 1][0] : 0)) % MOD;
}
}
return (f[zero][one][0] + f[zero][one][1]) % MOD;
}
};
java 解法, 执行用时: 18 ms, 内存消耗: 43.8 MB, 提交时间: 2024-05-01 10:51:26
class Solution {
public int numberOfStableArrays(int zero, int one, int limit) {
final int MOD = 1_000_000_007;
int[][][] f = new int[zero + 1][one + 1][2];
for (int i = 1; i <= Math.min(limit, zero); i++) {
f[i][0][0] = 1;
}
for (int j = 1; j <= Math.min(limit, one); j++) {
f[0][j][1] = 1;
}
for (int i = 1; i <= zero; i++) {
for (int j = 1; j <= one; j++) {
// + MOD 保证答案非负
f[i][j][0] = (int) (((long) f[i - 1][j][0] + f[i - 1][j][1] + (i > limit ? MOD - f[i - limit - 1][j][1] : 0)) % MOD);
f[i][j][1] = (int) (((long) f[i][j - 1][0] + f[i][j - 1][1] + (j > limit ? MOD - f[i][j - limit - 1][0] : 0)) % MOD);
}
}
return (f[zero][one][0] + f[zero][one][1]) % MOD;
}
}
python3 解法, 执行用时: 398 ms, 内存消耗: 28.9 MB, 提交时间: 2024-05-01 10:50:38
class Solution:
def numberOfStableArrays(self, zero: int, one: int, limit: int) -> int:
MOD = 1_000_000_007
@cache # 缓存装饰器，避免重复计算 dfs 的结果（记忆化）
# dfs(i,j,k) 表示用 i 个 0 和 j 个 1 构造稳定数组的方案数，
# 其中第 i+j 个位置要填 k，其中 k 为 0 或 1。
def dfs(i: int, j: int, k: int) -> int:
if i == 0:
return 1 if k == 1 and j <= limit else 0
if j == 0:
return 1 if k == 0 and i <= limit else 0
if k == 0:
return (dfs(i - 1, j, 0) + dfs(i - 1, j, 1) - (dfs(i - limit - 1, j, 1) if i > limit else 0)) % MOD
else: # else 可以去掉，这里仅仅是为了代码对齐
return (dfs(i, j - 1, 0) + dfs(i, j - 1, 1) - (dfs(i, j - limit - 1, 0) if j > limit else 0)) % MOD
ans = (dfs(zero, one, 0) + dfs(zero, one, 1)) % MOD
dfs.cache_clear() # 防止爆内存
return ans
# 递推
def numberOfStableArrays2(self, zero: int, one: int, limit: int) -> int:
MOD = 1_000_000_007
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):
f[i][j][0] = (f[i - 1][j][0] + f[i - 1][j][1] - (f[i - limit - 1][j][1] if i > limit else 0)) % MOD
f[i][j][1] = (f[i][j - 1][0] + f[i][j - 1][1] - (f[i][j - limit - 1][0] if j > limit else 0)) % MOD
return sum(f[-1][-1]) % MOD