题目链接：https://leetcode.cn/problems/find-all-possible-stable-binary-arrays-i/description/
题目大意：给出三个数zero, one, limit，求满足以下条件的数组的数目：
- 数组中有
zero个0和one个1 - 任何长度大于等于
limit+1的子数组中都必须包含0和1
思路：刚开始想的是往zero个0里插入one个1，找方案数。但不知道怎么满足第二个条件。一看题解是DP，昏了。还是三重DP，这哪想得出来。
不过看了题解后还是比较清晰的，毕竟重点是搞清楚状态转移方程。
设dp0[i][j]是包含i个0和j个1且以0结尾的合法的长度为i+j的数组的数目；dp1[i][j]是包含i个0和j个1且以1结尾的合法的长度为i+j的数组的数目。那么显然结果就是dp0[zero][one] + dp1[zero][one]
那么如何转移状态呢？
dp0[i][j]数组是以0结尾的，那么把这个0还回去，找上一个状态。显然要从dp0[i-1][j]和dp1[i-1][j]来找，因为上一个数组必然是包含i-1个0和j个1的。
对于dp1[i-1][j]，这是OK的，因为这时上一个数组的结尾是1，当前数组结尾是0，必然可以直接转移，全部加上。
对于dp0[i-1][j]，上一个数组结尾为0，那么要排除这种情况：前面已经连续出现了limit个0（包括上一个数组的结尾0），那么在这一连串0之前必然是一个1（否则上一个数组就已经不合法了）。这种情况的数目是dp1[i-limit-1][j]。其他的可以安全加上。
因此状态转移是这样的：
dp0[i][j] = dp1[i-1][j] + dp0[i-1][j];if (i > limit) {dp0[i][j] -= dp1[i-limit-1][j];}dp0[i][j] = (dp0[i][j] % MOD + MOD) % MOD;
那么dp1[i][j]的转移，就是把i和j对调一下。
dp1[i][j] = dp0[i][j-1] + dp1[i][j-1];if (j > limit) {dp1[i][j] -= dp0[i][j-limit-1];}dp1[i][j] = (dp1[i][j] % MOD + MOD) % MOD;
然后考虑边界情况，刚开始时应该把dp0[i][0]在i <= limit && i <= zero时都置为1，因为这时只有1种方法，就是全0，并且合法。对于dp1[0][j]同理。
至于dp0[0][j]和dp1[i][0]在任何时候都是不合法的，因为违背了定义要以0或者1结尾，这些置0即可。
完整代码
class Solution {
public:int numberOfStableArrays(int zero, int one, int limit) {const int MOD = 1000000007;vector<vector<int>> dp0(zero+1, vector<int>(one+1, 0));vector<vector<int>> dp1(zero+1, vector<int>(one+1, 0));for (int i = 0; i <= min(limit, zero); i++)dp0[i][0] = 1;for (int j = 0; j <= min(limit, one); j++)dp1[0][j] = 1;for (int i = 1; i <= zero; i++) {for (int j = 1; j <= one; j++) {dp0[i][j] = dp1[i-1][j] + dp0[i-1][j];if (i > limit) {dp0[i][j] -= dp1[i-limit-1][j];}dp0[i][j] = (dp0[i][j] % MOD + MOD) % MOD;dp1[i][j] = dp0[i][j-1] + dp1[i][j-1];if (j > limit) {dp1[i][j] -= dp0[i][j-limit-1];}dp1[i][j] = (dp1[i][j] % MOD + MOD) % MOD;}}return (dp0[zero][one] + dp1[zero][one]) % MOD;}
};
