题目链接:https://leetcode.cn/problems/find-all-possible-stable-binary-arrays-i/description/

题目大意:给出三个数zero, one, limit,求满足以下条件的数组的数目:

  • 数组中有zero0one1
  • 任何长度大于等于limit+1的子数组中都必须包含01

思路:刚开始想的是往zero0里插入one1,找方案数。但不知道怎么满足第二个条件。一看题解是DP,昏了。还是三重DP,这哪想得出来。

不过看了题解后还是比较清晰的,毕竟重点是搞清楚状态转移方程。

dp0[i][j]是包含i0j1且以0结尾的合法的长度为i+j的数组的数目;dp1[i][j]是包含i0j1且以1结尾的合法的长度为i+j的数组的数目。那么显然结果就是dp0[zero][one] + dp1[zero][one]

那么如何转移状态呢?
dp0[i][j]数组是以0结尾的,那么把这个0还回去,找上一个状态。显然要从dp0[i-1][j]dp1[i-1][j]来找,因为上一个数组必然是包含i-10j1的。

对于dp1[i-1][j],这是OK的,因为这时上一个数组的结尾是1,当前数组结尾是0,必然可以直接转移,全部加上。

对于dp0[i-1][j],上一个数组结尾为0,那么要排除这种情况:前面已经连续出现了limit0(包括上一个数组的结尾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]的转移,就是把ij对调一下。

				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;
    }
};

10-10 17:09