目标
给你 3 个正整数 zero ，one 和 limit 。
一个 二进制数组 arr 如果满足以下条件，那么我们称它是 稳定的 ：
- 0 在 arr 中出现次数 恰好 为 zero 。
- 1 在 arr 中出现次数 恰好 为 one 。
- arr 中每个长度超过 limit 的 子数组 都 同时 包含 0 和 1 。
请你返回 稳定 二进制数组的 总 数目。
由于答案可能很大，将它对 10^9 + 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 medium
- 1 <= zero, one, limit <= 1000 hard
提示：
- Let
dp[a][b][c = 0/1][d]be the number of stable arrays with exactly a 0s, b 1s and consecutive d value of c’s at the end. - Try each case by appending a 0/1 at last to get the inductions.
思路
有 zero 个 0 和 one 个 1 组成的数组，满足所有长度大于 limit 的子数组同时包含0和1的数组有多少个。
首先考虑由 zero 个 0 和 one 个 1 组成的数组有多少个。C(zero + one, zero) 从 zero + one 个位置中选出 zero 或者 one 个。根据题目中的范围 1 ~ 200，C(400, 200) 大概在 10^119 ~ 10^120之间。不可能枚举所有组合，更别提枚举每种组合的所有子数组了。我们必须自底向上寻求解决方案。
如何保证 limit + 1 的窗口内一定包含 0 和 1 呢？
看了提示说是四维动态规划，直接放弃了。思考过程中卡住的点是不会构建满足条件的解，想不出怎样才能让子数组中同时包含 0 和 1。其实只要保证不出现连续 limit + 1 个 0 或 1 就可以了。想到了动态规划，但是不知道如何进行状态转移。
代码