找出所有稳定的二进制数组 Ⅱ。用go语言，请实现一个函数，接收三个正整数 zero、one 和 limit 作为输入。函数的任务是计算符合以下条件的稳定二进制数组的数量：
1.数组中的 0 的个数正好为 zero。
2.数组中的 1 的个数正好为 one。
3.数组中每个长度超过 limit 的子数组都同时包含 0 和 1。
计算出符合条件的稳定二进制数组的总数，并返回对 1000000007 取模后的结果。
1 <= zero, one, limit <= 1000。
输入：zero = 1, one = 1, limit = 2。
输出：2。
解释：
两个稳定的二进制数组为 [1,0] 和 [0,1] ，两个数组都有一个 0 和一个 1 ，且没有子数组长度大于 2 。
大体步骤如下：
1.初始化一个三维数组 dp 来保存中间计算结果，其中 dp[i][j][k] 表示 0 的个数为 i，1 的个数为 j，最后一个数字是 k 的稳定二进制数组的数量。
2.遍历 i 从 0 到 zero，j 从 0 到 one，k 从 0 到 1：
- 如果
i等于 0：若lastBit为 0 或者j大于limit，则dp[i][j][lastBit]设为 0，否则设为 1。 - 如果
j等于 0：若lastBit为 1 或者i大于limit，则dp[i][j][lastBit]设为 0，否则设为 1。 - 否则，更新
dp[i][j][lastBit]的值，根据前一个状态计算当前稳定数组数量，并考虑限制条件。
3.对于更新后的 dp[i][j][lastBit] 进行取模操作，并处理可能的负数情况。
4.返回 (dp[zero][one][0] + dp[zero][one][1]) % MOD 作为结果。
时间复杂度分析：
- 遍历三维数组的时间复杂度为 O(zero \* one \* 2)，这里表示为 O(n^3)，其中 n 表示输入参数中的最大值。
- 每个状态更新的操作都是常数时间复杂度的，因此总的时间复杂度为 O(n^3)。
空间复杂度分析：
- 三维数组
dp的空间复杂度为 O(zero \* one \* 2)，即 O(n^3)。 - 其他额外变量占用的空间可以忽略不计，因此总的额外空间复杂度为 O(n^3)。
Go完整代码如下：
package main
import (
"fmt"
)
const MOD = 1000000007
func numberOfStableArrays(zero int, one int, limit int) int {
dp := make([][][]int, zero + 1)
for i := range dp {
dp[i] = make([][]int, one + 1)
for j := range dp[i] {
dp[i][j] = make([]int, 2)
}
}
for i := 0; i <= zero; i++ {
for j := 0; j <= one; j++ {
for lastBit := 0; lastBit <= 1; lastBit++ {
if i == 0 {
if lastBit == 0 || j > limit {
dp[i][j][lastBit] = 0
} else {
dp[i][j][lastBit] = 1
}
} else if j == 0 {
if lastBit == 1 || i > limit {
dp[i][j][lastBit] = 0
} else {
dp[i][j][lastBit] = 1
}
} else if lastBit == 0 {
dp[i][j][lastBit] = dp[i - 1][j][0] + dp[i - 1][j][1]
if i > limit {
dp[i][j][lastBit] -= dp[i - limit - 1][j][1]
}
} else {
dp[i][j][lastBit] = dp[i][j - 1][0] + dp[i][j - 1][1]
if j > limit {
dp[i][j][lastBit] -= dp[i][j - limit - 1][0]
}
}
dp[i][j][lastBit] %= MOD
if dp[i][j][lastBit] < 0 {
dp[i][j][lastBit] += MOD
}
}
}
}
return (dp[zero][one][0] + dp[zero][one][1]) % MOD
}
func main() {
zero := 1
one := 1
limit := 2
fmt.Println(numberOfStableArrays(zero, one, limit))
}
Rust完整代码如下：
const MOD: i64 = 1_000_000_007;
fn number_of_stable_arrays(zero: i32, one: i32, limit: i32) -> i64 {
let mut dp = vec![vec![vec![0; 2]; (one + 1) as usize]; (zero + 1) as usize];
for i in 0..=zero {
for j in 0..=one {
for last_bit in 0..=1 {
if i == 0 {
if last_bit == 0 || j > limit {
dp[i as usize][j as usize][last_bit as usize] = 0;
} else {
dp[i as usize][j as usize][last_bit as usize] = 1;
}
} else if j == 0 {
if last_bit == 1 || i > limit {
dp[i as usize][j as usize][last_bit as usize] = 0;
} else {
dp[i as usize][j as usize][last_bit as usize] = 1;
}
} else if last_bit == 0 {
dp[i as usize][j as usize][last_bit as usize] =
dp[(i - 1) as usize][j as usize][0] + dp[(i - 1) as usize][j as usize][1];
if i > limit {
dp[i as usize][j as usize][last_bit as usize] -=
dp[(i - limit - 1) as usize][j as usize][1];
}
} else {
dp[i as usize][j as usize][last_bit as usize] =
dp[i as usize][(j - 1) as usize][0] + dp[i as usize][(j - 1) as usize][1];
if j > limit {
dp[i as usize][j as usize][last_bit as usize] -=
dp[i as usize][(j - limit - 1) as usize][0];
}
}
dp[i as usize][j as usize][last_bit as usize] %= MOD;
if dp[i as usize][j as usize][last_bit as usize] < 0 {
dp[i as usize][j as usize][last_bit as usize] += MOD;
}
}
}
}
return (dp[zero as usize][one as usize][0] + dp[zero as usize][one as usize][1]) % MOD;
}
fn main() {
let zero = 1;
let one = 1;
let limit = 2;
println!("{}", number_of_stable_arrays(zero, one, limit));
}
