leetcode 2026-03-09 每日一练 - 找出所有稳定的二进制数组 I

题目描述

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

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

如果一个二进制数组满足：

  • 0 的个数恰好是 zero
  • 1 的个数恰好是 one
  • 任意长度大于 limit 的子数组都同时包含 0 和 1

则称该数组是稳定的。

请返回稳定二进制数组的总数，答案对 1e9+7 取模。

示例 1：

  • 输入：zero = 1, one = 1, limit = 2
  • 输出：2

示例 2：

  • 输入：zero = 1, one = 2, limit = 1
  • 输出：1

示例 3：

  • 输入：zero = 3, one = 3, limit = 2
  • 输出：14

解题思路

这题本质是一个“带连续段限制”的计数 DP。

方法一：记忆化搜索

定义 dfs(i, j, k)：

  • 还剩 i 个 0、j 个 1 可用
  • 当前这个位置要填的数字是 k（k=0 或 k=1）
  • 返回满足条件的方案数

最终答案：

dfs(zero, one, 0) + dfs(zero, one, 1)。

关键转移（以 k=0 为例）：

  • 正常拼接来源：dfs(i-1, j, 0) 和 dfs(i-1, j, 1)
  • 但其中包含了“连续 0 超过 limit”的非法情况
  • 非法部分正好是：倒数 limit+1 个都是 0，即要减去 dfs(i-limit-1, j, 1)

k=1 对称处理即可。

代码实现（方法一：记忆化搜索）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
func numberOfStableArrays(zero int, one int, limit int) int {
    const mod int = 1e9 + 7

    // f[i][j][k] 记忆化数组：
    // i 个 0、j 个 1、当前填 k 时的方案数。
    // -1 表示还没计算。
    f := make([][][2]int, zero+1)
    for i := range f {
        f[i] = make([][2]int, one+1)
        for j := range f[i] {
            f[i][j] = [2]int{-1, -1}
        }
    }

    var dfs func(i, j, k int) int
    dfs = func(i, j, k int) int {
        // 越界：没有可行方案。
        if i < 0 || j < 0 {
            return 0
        }

        // 没有 0 可用了：只有在当前要求填 1 且 j 不超过 limit 时合法。
        if i == 0 {
            if k == 1 && j <= limit {
                return 1
            }
            return 0
        }

        // 没有 1 可用了：只有在当前要求填 0 且 i 不超过 limit 时合法。
        if j == 0 {
            if k == 0 && i <= limit {
                return 1
            }
            return 0
        }

        // 记忆化命中。
        res := &f[i][j][k]
        if *res != -1 {
            return *res
        }

        if k == 0 {
            // 当前位置填 0：
            // 总来源 = 前一位填 0 + 前一位填 1
            // 减去非法来源：连续 0 长度超过 limit 的情况
            *res = (dfs(i-1, j, 0) + dfs(i-1, j, 1) - dfs(i-limit-1, j, 1) + mod) % mod
        } else {
            // 对称处理 1。
            *res = (dfs(i, j-1, 0) + dfs(i, j-1, 1) - dfs(i, j-limit-1, 0) + mod) % mod
        }
        return *res
    }

    return (dfs(zero, one, 0) + dfs(zero, one, 1)) % mod
}

方法二：动态规划

把记忆化搜索改写成迭代 DP。

定义 f[i][j][k]：

  • 使用 i 个 0、j 个 1
  • 且最后一个数字是 k
  • 的稳定数组数量

答案是 f[zero][one][0] + f[zero][one][1]。

初始化：

  • f[i][0][0] = 1，1 <= i <= min(limit, zero)
  • f[0][j][1] = 1，1 <= j <= min(limit, one)

转移方程：

  • f[i][j][0] = f[i-1][j][0] + f[i-1][j][1] - f[i-limit-1][j][1]
  • f[i][j][1] = f[i][j-1][0] + f[i][j-1][1] - f[i][j-limit-1][0]

同样注意取模与负数修正。

核心细节

  1. 状态定义里保留最后一位/当前位信息：否则没法判断是否连续超过 limit。
  2. “减去非法项”是关键：这题最容易漏掉这一步，导致把超长连续段也计入答案。
  3. 取模防负数：(a - b + mod) % mod 不能省。
  4. 边界 i<0 或 j<0 返回 0：避免越界状态污染结果。

复杂度分析

设 Z = zero，O = one。

  • 时间复杂度：O(Z * O)
  • 空间复杂度：O(Z * O)

记忆化和 DP 本质状态数一致，复杂度同阶。

边界情况与自测用例

建议至少覆盖这些测试：

  1. zero = 1, one = 1, limit = 1，答案应为 2（01、10）。
  2. zero = 3, one = 0, limit = 2，答案应为 0（连续 0 超限）。
  3. zero = 2, one = 0, limit = 2，答案应为 1（00）。
  4. zero = 0, one = 3, limit = 2，答案应为 0（连续 1 超限）。
  5. zero = 0, one = 2, limit = 2，答案应为 1（11）。

这些用例可以快速验证：

  • 边界是否正确
  • 减法去重是否正确
  • 模运算是否安全

总结

这题是“计数 + 连续段限制”的经典模型。

记忆化搜索更直观，动态规划更适合模板化实现。两者核心都在于：

  • 按最后一位拆状态
  • 用“总来源 - 非法来源”控制连续段长度

参考资料

  • 作者：ylb
  • 链接：https://leetcode.cn/problems/find-all-possible-stable-binary-arrays-i/solutions/2870488/python3javacgotypescript-yi-ti-shuang-ji-vhlz/
  • 来源：力扣（LeetCode）