2024-12-08：找出所有稳定的二进制数组 Ⅱ。用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 。

答案2024-12-08：

chatgpt

题目来自leetcode3130。

大体步骤如下：

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));
}