class Solution {
public:
int numberOfStableArrays(int zero, int one, int limit) {
}
};
3130. 找出所有稳定的二进制数组 II
给你 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 <= 1000原站题解
rust 解法, 执行用时: 573 ms, 内存消耗: 55.8 MB, 提交时间: 2024-08-07 09:50:53
const MOD: i32 = 1000000007;
impl Solution {
pub fn number_of_stable_arrays(zero: i32, one: i32, limit: i32) -> i32 {
let mut memo = vec![vec![vec![-1; 2]; (one + 1) as usize]; (zero + 1) as usize];
fn dp(zero: usize, one: usize, last_bit: usize, limit: usize, memo: &mut Vec<Vec<Vec<i32>>>) -> i32 {
if zero == 0 {
return if last_bit == 0 || one > limit { 0 } else { 1 };
} else if one == 0 {
return if last_bit == 1 || zero > limit { 0 } else { 1 };
}
if memo[zero][one][last_bit] == -1 {
let mut res = 0;
if last_bit == 0 {
res = (dp(zero - 1, one, 0, limit, memo) + dp(zero - 1, one, 1, limit, memo)) % MOD;
if zero > limit {
res = (res - dp(zero - limit - 1, one, 1, limit, memo) + MOD) % MOD;
}
} else {
res = (dp(zero, one - 1, 0, limit, memo) + dp(zero, one - 1, 1, limit, memo)) % MOD;
if one > limit {
res = (res - dp(zero, one - limit - 1, 0, limit, memo) + MOD) % MOD;
}
}
memo[zero][one][last_bit] = res % MOD;
}
memo[zero][one][last_bit]
}
let zero = zero as usize;
let one = one as usize;
let limit = limit as usize;
(dp(zero, one, 0, limit, &mut memo) + dp(zero, one, 1, limit, &mut memo)) % MOD
}
}
golang 解法, 执行用时: 220 ms, 内存消耗: 33.4 MB, 提交时间: 2024-05-01 10:52:51
func numberOfStableArrays(zero, one, limit int) int {
const mod = 1_000_000_007
memo := make([][][2]int, zero+1)
for i := range memo {
memo[i] = make([][2]int, one+1)
for j := range memo[i] {
memo[i][j] = [2]int{-1, -1}
}
}
var dfs func(int, int, int) int
dfs = func(i, j, k int) (res int) {
if i == 0 { // 递归边界
if k == 1 && j <= limit {
return 1
}
return
}
if j == 0 { // 递归边界
if k == 0 && i <= limit {
return 1
}
return
}
p := &memo[i][j][k]
if *p != -1 { // 之前计算过
return *p
}
if k == 0 {
// +mod 保证答案非负
res = (dfs(i-1, j, 0) + dfs(i-1, j, 1)) % mod
if i > limit {
res = (res - dfs(i-limit-1, j, 1) + mod) % mod
}
} else {
res = (dfs(i, j-1, 0) + dfs(i, j-1, 1)) % mod
if j > limit {
res = (res - dfs(i, j-limit-1, 0) + mod) % mod
}
}
*p = res // 记忆化
return
}
return (dfs(zero, one, 0) + dfs(zero, one, 1)) % mod
}
cpp 解法, 执行用时: 317 ms, 内存消耗: 89.8 MB, 提交时间: 2024-05-01 10:52:05
class Solution {
int MOD = 1'000'000'007;
vector<vector<array<int, 2>>> memo;
int dfs(int i, int j, int k, int limit) {
if (i == 0) { // 递归边界
return k == 1 && j <= limit;
}
if (j == 0) { // 递归边界
return k == 0 && i <= limit;
}
int& res = memo[i][j][k]; // 注意这里是引用
if (res != -1) { // 之前计算过
return res;
}
if (k == 0) {
// + MOD 保证答案非负
res = ((long long) dfs(i - 1, j, 0, limit) + dfs(i - 1, j, 1, limit) +
(i > limit ? MOD - dfs(i - limit - 1, j, 1, limit) : 0)) % MOD;
} else {
res = ((long long) dfs(i, j - 1, 0, limit) + dfs(i, j - 1, 1, limit) +
(j > limit ? MOD - dfs(i, j - limit - 1, 0, limit) : 0)) % MOD;
}
return res;
}
public:
int numberOfStableArrays(int zero, int one, int limit) {
// -1 表示没有计算过
memo.resize(zero + 1, vector<array<int, 2>>(one + 1, {-1, -1}));
return (dfs(zero, one, 0, limit) + dfs(zero, one, 1, limit)) % MOD;
}
};
java 解法, 执行用时: 453 ms, 内存消耗: 96.1 MB, 提交时间: 2024-05-01 10:51:47
class Solution {
private static final int MOD = 1_000_000_007;
public int numberOfStableArrays(int zero, int one, int limit) {
int[][][] memo = new int[zero + 1][one + 1][2];
for (int[][] m : memo) {
for (int[] m2 : m) {
Arrays.fill(m2, -1); // -1 表示没有计算过
}
}
return (dfs(zero, one, 0, limit, memo) + dfs(zero, one, 1, limit, memo)) % MOD;
}
private int dfs(int i, int j, int k, int limit, int[][][] memo) {
if (i == 0) { // 递归边界
return k == 1 && j <= limit ? 1 : 0;
}
if (j == 0) { // 递归边界
return k == 0 && i <= limit ? 1 : 0;
}
if (memo[i][j][k] != -1) { // 之前计算过
return memo[i][j][k];
}
if (k == 0) {
// + MOD 保证答案非负
memo[i][j][k] = (int) (((long) dfs(i - 1, j, 0, limit, memo) + dfs(i - 1, j, 1, limit, memo) +
(i > limit ? MOD - dfs(i - limit - 1, j, 1, limit, memo) : 0)) % MOD);
} else {
memo[i][j][k] = (int) (((long) dfs(i, j - 1, 0, limit, memo) + dfs(i, j - 1, 1, limit, memo) +
(j > limit ? MOD - dfs(i, j - limit - 1, 0, limit, memo) : 0)) % MOD);
}
return memo[i][j][k];
}
}
python3 解法, 执行用时: 9753 ms, 内存消耗: 367.3 MB, 提交时间: 2024-05-01 10:51:02
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