当前位置：首页 > news >正文

dp+容斥原理，LeetCode 3130. 找出所有稳定的二进制数组 II

news 来源：原创 2024/9/19 3:07:00

一、题目

1、题目描述

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

一个

二进制数组
arr 如果满足以下条件，那么我们称它是 稳定的 ：
0 在 arr 中出现次数恰好为 zero 。
1 在 arr 中出现次数恰好为 one 。
arr 中每个长度超过 limit 的
子数组
都同时包含 0 和 1 。

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

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

2、接口描述

python3

class Solution:def numberOfStableArrays(self, zero: int, one: int, limit: int) -> int:

c++

class Solution {
public:int numberOfStableArrays(int zero, int one, int limit) {}
};

C#

public class Solution {public int NumberOfStableArrays(int zero, int one, int limit) {}
}

3、原题链接

3130. 找出所有稳定的二进制数组 II

二、解题报告

1、思路分析

定义状态f(i, j, k) 为用 i 个0，j 个 1，并且最后一个为k的合法方案数（即没有连续limit 以上相同的0或者1）

那么如何状态转移？

当前是0/1，前一个自然也可以是0/1

以f(i, j, 0)为例，我们当前的0可以加在f(i - 1, j, 0) 和 f(i, j - 1, 0) 后面，显然会出现非法情况，即接上一个0，出现大于连续limit个0，所以要减去加上这个0后，最大连续0为limit + 1的情况

因为定义的状态为合法方案，所以合法方案加上1个0出现的非法方案只可能是limit + 1个连续0的情况，并且这limit + 1 个0是后缀

即我们要减去 f(i - limit - 1, j, 1)，因为后缀是limit + 1个0，后缀0前面一定是1

于是有了状态转移方程：

f[i][j][0] = (f[i - 1][j][0] + f[i - 1][j][1] - (f[i - limit - 1][j][1] if i > limit else 0)
f[i][j][1] = f[i][j - 1][0] + f[i][j - 1][1] - (f[i][j - limit - 1][0] if j > limit else 0)

总结：其实就是将方案划分为不重不漏的状态集合，利用容斥原理完成状态转移

2、复杂度

时间复杂度： O(zero * one)空间复杂度：O(zero * one)

3、代码详解

python3

P = 1_000_000_007
class Solution:def numberOfStableArrays(self, zero: int, one: int, limit: int) -> int:f = [[[0] * 2 for j in range(one + 1)] for i in range(zero + 1)]for j in range(1, min(one + 1, limit + 1)):f[0][j][1] = 1for i in range(1, min(zero + 1, limit + 1)):f[i][0][0] = 1for i in range(1, zero + 1):for j in range(1, one + 1):f[i][j][0] = (f[i - 1][j][0] + f[i - 1][j][1] - (f[i - limit - 1][j][1] if i > limit else 0)) % Pf[i][j][1] = (f[i][j - 1][0] + f[i][j - 1][1] - (f[i][j - limit - 1][0] if j > limit else 0)) % Preturn (f[zero][one][0] + f[zero][one][1]) % P

c++

constexpr int P = 1'000'000'007;
class Solution {
public:int numberOfStableArrays(int zero, int one, int limit) {std::vector<std::vector<std::array<int, 2>>> f(zero + 1, std::vector<std::array<int, 2>>(one + 1));for (int i = 1; i <= std::min(zero, limit); ++ i)f[i][0][0] = 1;for (int i = 1; i <= std::min(one, limit); ++ i)f[0][i][1] = 1;for (int i = 1; i <= zero; ++ i)for (int j = 1; j <= one; ++ j) {f[i][j][0] = (1LL * f[i - 1][j][0] + f[i - 1][j][1] - (i > limit ? f[i - limit - 1][j][1] : 0)) % P;f[i][j][0] = (1LL * f[i][j][0] + P) % P;f[i][j][1] = (1LL * f[i][j - 1][0] + f[i][j - 1][1] - (j > limit ? f[i][j - limit - 1][0] : 0)) % P;f[i][j][1] = (1LL * f[i][j][1] + P) % P;}return (1LL * f[zero][one][0] + f[zero][one][1]) % P;}
};

C#

public class Solution {const int P = 1000000007;public int NumberOfStableArrays(int zero, int one, int limit) {int[,,] f = new int[zero + 1, one + 1, 2];for (int i = 1; i <= Math.Min(zero, limit); ++ i)f[i, 0, 0] = 1;for (int i = 1; i <= Math.Min(one, limit); ++ i)f[0, i, 1] = 1;for (int i = 1; i <= zero; ++ i)for (int j = 1; j <= one; ++ j) {f[i, j, 0] = (int)(((long)f[i - 1, j, 0] + f[i - 1, j, 1] - (i > limit ? f[i - limit - 1, j, 1] : 0)) % P);f[i, j, 0] = (int)(((long)f[i, j, 0] + P) % P);f[i, j, 1] = (int)(((long)f[i, j - 1, 0] + f[i, j - 1, 1] - (j > limit ? f[i, j - limit - 1, 0] : 0)) % P);f[i, j, 1] = (int)(((long)f[i, j, 1] + P) % P);}return (int)(((long)f[zero, one, 0] + f[zero, one, 1]) % P);}
}