登录逐步优化 DP 状态
前记：读了读别人的题解，感觉 newhar 老师的思路更清晰易懂一点，推荐大家看 newhar 的题解，这里就记一下自己的解法。
解法：DP
以下题解中把 limit 简记为 $l$。
转化题目条件
首先，题目要求序列中恰好出现 zero 个 $0$ 以及 one 个 $1$，显然序列的长度必须为 zero + one。记序列的长度为 $n$。
只要一个子数组包含 $0$ 和 $1$，那么所有完全包含它的子数组也会包含 $0$ 和 $1$。因此，题目中“arr 中每个长度超过 $l$ 的子数组都同时包含 $0$ 和 $1$”这一条件可以重写为：
arr中每个长度恰为 $(l + 1)$ 的子数组都同时包含 $0$ 和 $1$。
设计 DP 状态
考虑任一下标 $i$，假设 $i$ 左边最近的 $0$ 到 $i$ 的距离是 $p_i$（$p_i = 0$ 说明 arr[i] == 0），$i$ 左边最近的 $1$ 到 $i$ 的距离是 $q_i$（$q_i = 0$ 说明 arr[i] == 1）。不妨假设下标 $i$ 是某个长度为 $(l + 1)$ 的子数组的右端点，因为这个子数组里既有 $0$ 又有 $1$，那么我们同时有 $p_i \le l$ 以及 $q_i \le l$。
由此可以设计出朴素的 DP 状态。设 $f(i, j, p, q)$ 表示考虑序列的前 $i$ 个元素中有 $j$ 个 $1$，且 $i$ 到最近的 $0$ 距离为 $p$，到最近的 $1$ 距离为 $q$ 的方案数。但这样状态总数为 $\mathcal{O}(n^2l^2)$，无论是 C 题还是 D 题都无法通过。
优化 DP 状态
注意到元素要么是 $0$ 要么是 $1$，也就是说对于任意的 $i$，$p = 0$ 和 $q = 0$ 恰有一个成立。因此可以将 DP 状态压缩为 $f(i, j, t = 0/1, d)$ 表示考虑序列的前 $i$ 个元素中有 $j$ 个 $1$，且第 $i$ 个元素填的是 $t$，$i$ 到最近的另一种元素（即 $1 - t$）距离为 $d$ 的方案数。这样状态总数为 $\mathcal{O}(n^2l)$。
转移方程分为两部分。
f(i, j, 0, d) += f(i - 1, j, 0, d - 1)
f(i, j, 1, d) += f(i - 1, j - 1, 1, d - 1)
这一部分的含义是，让第 $i$ 个元素和第 $(i - 1)$ 个元素相同，那么到另一种元素的距离自然增加 $1$。
f(i, j, 0, 1) += f(i - 1, j, 1, *)
f(i, j, 1, 1) += f(i - 1, j - 1, 0, *)
这一部分的含义是，让第 $i$ 个元素和第 $(i - 1)$ 个元素不同，那么到另一种元素（也就是上一个元素）的距离就是 $1$。这里的星号通过维护前缀和即可 $\mathcal{O}(1)$ 计算。
初值就是枚举第一个元素填 $0$ 还是 $1$。对于第一个元素来说，另一种元素已经 $1$ 个位置没出现了，所以 $d = 1$，即 $f(1, 0, 0, 1) = f(1, 1, 1, 1) = 1$。
整体复杂度 $\mathcal{O}(n^2l)$，可以通过 C 题。
继续优化 DP 状态
我们发现，DP 主要的运算复杂度来自转移方程的第一部分。第一部分的转移方程看起来很简单，好像只是把上一个位置所有 $(d - 1)$ 的 DP 值都照搬过来而已。由于 $d \le l$ 的限制，只是丢弃了 $f(i - 1, j, *, l)$ 的 DP 值。而 DP 方程的第二部分没有丢弃任何 DP 值，通过前缀和直接把所有情况照单全收。
这里其实在暗示我们：只要上个位置距离另一种元素的距离不到 $l$，那么当前位置无论填什么都是安全的。只有上个位置距离另一种元素的距离恰为 $l$ 时，当前位置必须填与上个位置不同的元素。也就是说：
（当前位置填元素 t 的方案数） = （上个位置的所有方案数） - （元素 1 - t 最近一次在 i - limit - 1 出现，从 i - limit 到 i 全部都是元素 t 的方案数）
设 $f(i, j, t = 0/1)$ 表示考虑序列的前 $i$ 个元素中有 $j$ 个 $1$，且第 $i$ 个元素填的是 $t$ 的方案数。“元素 $(1 - t)$ 最近一次在 $(i - l - 1)$ 出现，从 $(i - l)$ 到 $i$ 全部都是元素 $t$ 的方案数”怎么算呢？当然就是 $f(i - l - 1, j', 1 - t)$。这里 $j'$ 要看如果 $t = 0$ 那么 $j' = j$，否则如果 $t = 1$ 那么由于从 $(i - l)$ 到 $i$ 全部都是 $1$，则 $j' = j - l - 1$。
由此得到转移方程.
f(i, j, 0) = f(i - 1, j, 0) + f(i - 1, j, 1) - f(i - l - 1, j, 1)
f(i, j, 1) = f(i - 1, j - 1, 0) + f(i - 1, j - 1, 1) - f(i - l - 1, j - l - 1, 0)
整体复杂度 $\mathcal{O}(n^2)$，可以通过 D 题。
但是，实现过程中有一个初值的细节问题。当 $i = l + 1$ 时，我们要求 “元素 $(1 - t)$ 最近一次在下标 $0$ 出现的方案数”。空序列一定是合法的，所以有 $f(0, 0, 0) = f(0, 0, 1) = 1$。然而当 $i = 1$ 的时候，这样的初值设置会导致 $f(i - 1, j, 0) + f(i - 1, j, 1)$ 这部分的转移方程出现重复计算，所以我们直接继续设置初值 $f(1, 0, 0) = f(1, 1, 1) = 1$。
参考代码（c++）
###c++
class Solution {
public:
int numberOfStableArrays(int zero, int one, int limit) {
const int MOD = 1e9 + 7;
int n = zero + one;
long long g[n + 1][one + 1][2];
memset(g, 0, sizeof(g));
g[0][0][0] = g[0][0][1] = g[1][0][0] = g[1][1][1] = 1;
auto update = [&](long long &x, long long y) {
x = (x + y) % MOD;
};
for (int i = 2; i <= n; i++) {
for (int j = 0; j <= one; j++) {
update(g[i][j][0], g[i - 1][j][1] + g[i - 1][j][0]);
if (i > limit) update(g[i][j][0], MOD - g[i - 1 - limit][j][1]);
if (j > 0) update(g[i][j][1], g[i - 1][j - 1][0] + g[i - 1][j - 1][1]);
if (i > limit && j > limit) update(g[i][j][1], MOD - g[i - 1 - limit][j - 1 - limit][0]);
}
}
return (g[n][one][0] + g[n][one][1]) % MOD;
}
};
