题目：3130. 找出所有稳定的二进制数组 II
思路：大佬的思路
class Solution {
public:
int mod=1e9+7;
typedef long long LL;
LL sta[1010][1010][2];
//当前还有i个0、j个1时，第i+j的位置放置u,可以组成的合法数目
LL dfs(int i,int j,int u,int limit){
//当0、1中有数量为负数，说明此状态是不合法的
if(i<0||j<0) return 0;
//当0的数量为空时，后面就只能放置1了
if(i==0&&u==1&&j<=limit) return 1;
//当1的数量为空时，后面就只能放置0了
if(j==0&&u==0&&i<=limit) return 1;
//记忆化搜索
if(sta[i][j][u]!=-1) return sta[i][j][u];
LL res=0;
//当第i+j的位置放置0,那么下一个位置可以放置0和1，但是连续的0个数不能超过limit个，所以需要减掉不合法的情况
//因为dfs()返回的都是合法的情况，所以是减去dfs(i-1-limit,j,1,limit)
if(u==0){
res=(dfs(i-1,j,1,limit)+dfs(i-1,j,0,limit)-dfs(i-1-limit,j,1,limit))%mod;
}else{
res=(dfs(i,j-1,1,limit)+dfs(i,j-1,0,limit)-dfs(i,j-1-limit,0,limit))%mod;
}
return sta[i][j][u]=(res+mod)%mod;
}
int numberOfStableArrays(int zero, int one, int limit) {
memset(sta,-1,sizeof sta);
return (dfs(zero,one,1,limit)+dfs(zero,one,0,limit))%mod;
}
};