题目

给你 3 个正整数 zero ，one 和 limit 。

一个二进制数组 arr 如果满足以下条件，那么我们称它是 稳定的 ：

0 在 arr 中出现次数恰好为 zero 。
1 在 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

解题思路

我们可以定义一个三维数组 $dp[i][j][k]$，其中：

$i$ 表示当前数组中 0 的数量。
$j$ 表示当前数组中 1 的数量。
$k \in {0, 1}$ 表示数组最后一个元素的类型（即以 0 结尾或以 1 结尾）。

$dp[i][j][k]$ 的值代表正好使用 $i$ 个 0 和 $j$ 个 1，且末尾数字为 $k$ 的合法稳定二进制数组总数。

我们以计算 $dp[i][j][0]$（即在序列末尾追加一个 0）为例：

如果我们在一个包含 $i-1$ 个 0 和 $j$ 个 1 的合法数组末尾再追加一个 0，这个前置数组原本可能以 0 结尾，也可能以 1 结尾。

初步的转移思路是直接相加：

$$dp[i][j][0] = dp[i-1][j][0] + dp[i-1][j][1]$$

去除不合法情况（容斥处理）：

上述简单的相加会引入一种不合法的情况：追加这 1 个 0 之后，末尾恰好出现了 limit + 1 个连续的 0，破坏了“稳定”的条件。

这种情况何时发生？当且仅当在追加之前，原序列的末尾已经有了连续的 limit 个 0，且在这 limit 个 0 之前紧挨着的是一个 1。

这意味着，产生不合法情况的“前缀部分”，正是使用了 $i - limit - 1$ 个 0 和 $j$ 个 1，并且以 1 结尾的合法序列。其数量刚好等于 $dp[i - limit - 1][j][1]$。

因此，我们需要把这部分非法的数量减去。完整的状态转移方程如下：

以 0 结尾：如果 $i > limit$：$$dp[i][j][0] = dp[i-1][j][0] + dp[i-1][j][1] - dp[i - limit - 1][j][1]$$如果 $i \le limit$，则不会触发超限，直接相加即可。
以 1 结尾：如果 $j > limit$：$$dp[i][j][1] = dp[i][j-1][0] + dp[i][j-1][1] - dp[i][j - limit - 1][0]$$如果 $j \le limit$，同样直接相加。

(注意：在实际编码时，由于涉及减法，为了防止结果出现负数，需要对计算结果加上 $10^9 + 7$ 后再取余)

对于只包含单一数字的情况，只要长度不超过 limit，合法方案数都是 1：

对于所有 $1 \le x \le \min(limit, zero)$，初始化 $dp[x][0][0] = 1$。
对于所有 $1 \le y \le \min(limit, one)$，初始化 $dp[0][y][1] = 1$。
其余所有状态初始值为 0。
时间复杂度：$O(zero \times one)$。只需用两层嵌套循环遍历 0 和 1 的数量进行状态推导。题目给定的最大值是 200，总计算量大约只有 40,000 次运算，执行速度会非常快。
空间复杂度：$O(zero \times one)$。用于存储 DP 状态数组。如果需要极限优化，因为当前状态只依赖于 $i-1$ 和 $i - limit - 1$，空间复杂度还可以进一步压缩为一维或滑动窗口形式。

具体代码

class Solution:
    def numberOfStableArrays(self, zero: int, one: int, limit: int) -> int:
        MOD = 10**9 + 7
        
        # dp[i][j][0] 表示用了 i 个 0，j 个 1，且以 0 结尾的合法方案数
        # dp[i][j][1] 表示用了 i 个 0，j 个 1，且以 1 结尾的合法方案数
        # 初始化一个 (zero + 1) x (one + 1) x 2 的三维数组，全为 0
        dp = [[[0, 0] for _ in range(one + 1)] for _ in range(zero + 1)]
        
        # 边界条件初始化：处理只包含 0 或只包含 1 的情况
        # 只要长度不超过 limit，合法方案数都是 1
        for i in range(1, min(zero, limit) + 1):
            dp[i][0][0] = 1
            
        for j in range(1, min(one, limit) + 1):
            dp[0][j][1] = 1
            
        # 开始动态规划推导
        for i in range(1, zero + 1):
            for j in range(1, one + 1):
                
                # 1. 计算以 0 结尾的情况 (dp[i][j][0])
                # 第一步：盲目追加 0（前一个可能是 0 结尾，也可能是 1 结尾）
                dp[i][j][0] = (dp[i-1][j][0] + dp[i-1][j][1]) % MOD
                
                # 第二步：如果 0 的总数超过了 limit，减去恰好构成 limit + 1 个 0 的“违章建筑”
                if i > limit:
                    dp[i][j][0] = (dp[i][j][0] - dp[i - limit - 1][j][1] + MOD) % MOD
                    
                    
                # 2. 计算以 1 结尾的情况 (dp[i][j][1])
                # 第一步：盲目追加 1
                dp[i][j][1] = (dp[i][j-1][0] + dp[i][j-1][1]) % MOD
                
                # 第二步：如果 1 的总数超过了 limit，减去恰好构成 limit + 1 个 1 的“违章建筑”
                if j > limit:
                    dp[i][j][1] = (dp[i][j][1] - dp[i][j - limit - 1][0] + MOD) % MOD

        # 最终答案是将“以 0 结尾”和“以 1 结尾”的合法方案数相加
        return (dp[zero][one][0] + dp[zero][one][1]) % MOD

func numberOfStableArrays(zero int, one int, limit int) int {
    MOD := 1000000007

    // 在 Go 中初始化 3D 切片 (对应 Python 的 dp 数组)
    // dp[i][j][0] 表示用了 i 个 0，j 个 1，且以 0 结尾的合法方案数
    // dp[i][j][1] 表示用了 i 个 0，j 个 1，且以 1 结尾的合法方案数
    dp := make([][][2]int, zero+1)
    for i := range dp {
        dp[i] = make([][2]int, one+1)
    }

    // 初始化边界条件
    // Go 原生的 math.Min 只支持 float64，所以我们手动判断一下取最小值
    minZero := zero
    if limit < zero {
        minZero = limit
    }
    for i := 1; i <= minZero; i++ {
        dp[i][0][0] = 1
    }

    minOne := one
    if limit < one {
        minOne = limit
    }
    for j := 1; j <= minOne; j++ {
        dp[0][j][1] = 1
    }

    // 开始动态规划推导
    for i := 1; i <= zero; i++ {
        for j := 1; j <= one; j++ {
            
            // 1. 计算以 0 结尾的情况
            dp[i][j][0] = (dp[i-1][j][0] + dp[i-1][j][1]) % MOD
            if i > limit {
                // 减去违章建筑，加上 MOD 防止出现负数
                dp[i][j][0] = (dp[i][j][0] - dp[i-limit-1][j][1] + MOD) % MOD
            }

            // 2. 计算以 1 结尾的情况
            dp[i][j][1] = (dp[i][j-1][0] + dp[i][j-1][1]) % MOD
            if j > limit {
                // 减去违章建筑，加上 MOD 防止出现负数
                dp[i][j][1] = (dp[i][j][1] - dp[i][j-limit-1][0] + MOD) % MOD
            }
        }
    }

    // 返回总和并取模
    return (dp[zero][one][0] + dp[zero][one][1]) % MOD
}

3129. 找出所有稳定的二进制数组 I

beautifulremi

题目

解题思路

具体代码