LeetCode 3130 找出所有稳定的二进制数组II

方法1：动态规划

class Solution {
    public int numberOfStableArrays(int zero, int one, int limit) {
        int MOD = 1_000_000_007;
        int[][] dp0 = new int[zero + 1][one + 1];
        int[][] dp1 = new int[zero + 1][one + 1];
        for(int i = 0; i <= Math.min(zero, limit); i++)
            dp0[i][0] = 1;
        for(int j = 0; j <= Math.min(one, limit); 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];
                dp0[i][j] -= i > limit ? dp1[i - 1 - limit][j] : 0;
                dp0[i][j] = (dp0[i][j] % MOD + MOD) % MOD;
                dp1[i][j] = dp0[i][j - 1] + dp1[i][j - 1];
                dp1[i][j] -= j > limit ? dp0[i][j - 1 -limit] : 0;
                dp1[i][j] = (dp1[i][j] % MOD + MOD) % MOD;
            }
        }
        return (dp0[zero][one] + dp1[zero][one]) % MOD;
    }
}