【状态机动态规划】3129. 找出所有稳定的二进制数组 I

本文涉及知识点

动态规划汇总

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

给你 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

动态规划

动态规划的状态表示

pre[i][j][k] 已经解决了arr的前has个元素。以j个i结尾，整个arr包括k个0的数量。i $\in$ [0,1] j $\in$ [1,limit] k $
\in$[0,zero] 。
dp[i][j][k]记录 arr的前has+1个元素的状态。
空间复杂度： O(2 $\times$ limit $\times$ one )
不知道何种原因，总超出内存限制。 vector 换成原生数组就好了。

动态规划的转移方程

前置状态计算后置状态。三层循环枚举pre的状态，每种状态，分别枚举当前元素0和1。
确保j $\in$ [1,limit] ，0（1）不超过zero(one)。

动态规划的初始状态

pre[0][1][1] =1 pre[1][1][0]=1 其它全为0。

动态规划的填表顺序

has从2到zero+one。i,j,k且从小到大。

动态规划分返回值

pre之和。

动态规划代码

核心代码

class Solution {
public:
	int numberOfStableArrays(int zero, int one, int limit) {
		limit++;
		const int MOD = 1000000007;
		int pre[2][201][201] = { 0 };
		int dp[2][201][201] = { 0 };
		pre[0][1][1] = 1;
		pre[1][1][0] = 1;
		auto AddSelf = [&MOD](int& i1, int i2) {
			i1 = (i1 + i2) % MOD;
		};
		for (int has = 1; has < zero + one; has++) {
			memset(dp, 0, sizeof(dp));
			for (int j = 1; j < limit; j++) {//以0结尾
				for (int k = 0; k <= zero; k++) {
					const int iPre = pre[0][j][k];
					if (0 == iPre) { continue; }
					if ((j + 1 < limit) && (k + 1 <= zero)) {
						AddSelf(dp[0][j + 1][k + 1], iPre);
					}
					if (has - k + 1 <= one) {
						AddSelf(dp[1][1][k], iPre);
					}
				}
			}
			for (int j = 1; j < limit; j++) {//以0结尾
				for (int k = 0; k <= zero; k++) {
					const int iPre = pre[1][j][k];
					if (0 == iPre) { continue; }
					if ((j + 1 < limit) && (has - k + 1 <= one)) {//选1
						AddSelf(dp[1][j + 1][k], iPre);
					}
					if (k + 1 <= zero) {
						AddSelf(dp[0][1][k + 1], iPre);
					}
				}
			}
			memcpy(pre, dp, sizeof(dp));
		}
		int iRet = 0;
		for (int i = 0; i < 2; i++) {
			for (int j = 1; j < limit; j++) {//以0结尾
				for (int k = 0; k <= zero; k++) {
					AddSelf(iRet, pre[i][j][k]);
				}
			}
		}
		return iRet;
	}
};

测试用例

template<class T>
void Assert( vector<T> v1,  vector<T> v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		assert(v1[i] == v2[i]);
	}
}

template<class T>
void Assert(const T& t1, const T& t2)
{
	assert(t1 == t2);
}

int main()
{
	int zero,  one,  limit;
		
	{
		Solution slu;
		zero = 1, one = 1, limit = 2;
		auto res = slu.numberOfStableArrays(zero, one, limit);
		Assert(2, res);
	}
	{
		Solution slu;
		zero = 1, one = 2, limit = 1;
		auto res = slu.numberOfStableArrays(zero, one, limit);
		Assert(1, res);
	}
	{
		Solution slu;
		zero = 3, one = 3, limit = 2;
		auto res = slu.numberOfStableArrays(zero, one, limit);
		Assert(14, res);
	}
	{
		Solution slu;
		zero = 200, one = 200, limit = 200;
		auto res = slu.numberOfStableArrays(zero, one, limit);
		Assert(587893473, res);
	}
}

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

我想对大家说的话
《喜缺全书算法册》以原理、正确性证明、总结为主。
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛