Algorithm programming problem

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

Posted by farmer3-c on March 9, 2026
相关文章

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

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

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

  • 0 在 arr 中出现次数 恰好 为 zero 。
  • 1 在 arr 中出现次数 恰好 为 one 。
  • arr 中每个长度超过 limit 的 子数组 都 同时 包含 0 和 1 。

请你返回 稳定 二进制数组的 总 数目。

由于答案可能很大，将它对 $10^9 + 7$ 取余 后返回。

提示：

  • 1 <= zero, one, limit <= 200

思路

首先，这个问题是每个位有两个选择0/1，再加上限制limit,感觉就可以用dp做。

定义：

f[i][j][0] 为使用 i 个 0，j 个 1，且末尾为 0 的稳定数组个数；

f[i][j][1] 为使用 i 个 0，j 个 1，且末尾为 1 的稳定数组个数。

因为limit的限制，末尾连续0/1的数量不能超过它，f[i][j][0]为f[i-limit][j][0]~f[i-1][j][0]之和，f[i][j][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

class Solution {
public:
    int f[205][205][2] = {0};
    int numberOfStableArrays(int z, int o, int limit) {
        const int mod = 1e9 + 7;
        for (int i = 0; i <= z; i++) {
            f[i][0][0] = (i <= limit), f[i][0][1] = 0;
        }
        for (int i = 0; i <= o; i++) {
            f[0][i][0] = 0, f[0][i][1] = (i <= limit);
        }
        int sum1[o + 1];
        for (int j = 0; j <= o; j++) {
            sum1[j] = f[0][j][1];
        }
        for (int i = 1; i <= z; i++) {
            for (int j = 1, sum0 = f[i][0][0]; j <= o; j++) {
                f[i][j][0] = sum1[j];
                f[i][j][1] = sum0;

                sum0 = (sum0 + f[i][j][0]) % mod;
                if (j >= limit) {
                    sum0 = (sum0 + mod - f[i][j - limit][0]) % mod;
                }
                sum1[j] = (sum1[j] + f[i][j][1]) % mod;
                if (i >= limit) {
                    sum1[j] = (sum1[j] + mod - f[i - limit][j][1]) % mod;
                }
            }
        }
        return (f[z][o][0] + f[z][o][1]) % mod;
    }
};

参考

CATALOG