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