Leetcode-3129 找出所有稳定的二进制数组I
1. 题目描述
2. 解题思路
(1) 定义f[i][j][k]表示i个0、j个1且当前位i+j填写值为k=0/1的所有情况;
(2) 对于f[i][0][0]、f[0][j][1]初始化为1，注意到:
i
<
=
m
i
n
(
l
i
m
i
t
,
z
e
r
o
)
，
j
<
=
m
i
n
(
l
i
m
i
t
,
o
n
e
)
i<=min(limit,zero)，j<=min(limit,one)
i<=min(limit,zero)，j<=min(limit,one)
(3) 动态规划表达式:
f
[
i
]
[
j
]
[
0
]
=
(
f
[
i
−
1
]
[
j
]
[
0
]
+
f
[
i
−
1
]
[
j
]
[
1
]
+
(
i
>
limit
?
mod
−
f
[
i
−
limit
−
1
]
[
j
]
[
1
]
:
0
)
)
%
mod
f[i][j][0] = \left( f[i - 1][j][0] + f[i - 1][j][1] + \left( i > \text{limit} \, ? \, \text{mod} - f[i - \text{limit} - 1][j][1] : 0 \right) \right) \% \text{ mod}
f[i][j][0]=(f[i−1][j][0]+f[i−1][j][1]+(i>limit?mod−f[i−limit−1][j][1]:0))% mod
对于f[i-limit-1][j][1]表示在i+j-limit-1后存在着连续limit+1个0，这些为所有不合法情况，取mod避免结果为负数；
f
[
i
]
[
j
]
[
1
]
=
(
f
[
i
]
[
j
−
1
]
[
0
]
+
f
[
i
]
[
j
−
1
]
[
1
]
+
(
j
>
limit
?
mod
−
f
[
i
]
[
j
−
limit
−
1
]
[
0
]
:
0
)
)
%
mod
f[i][j][1] = \left( f[i][j - 1][0] + f[i][j - 1][1] + \left( j > \text{limit} ? \text{mod} - f[i][j - \text{limit} - 1][0] : 0 \right) \right) \% \text{mod}
f[i][j][1]=(f[i][j−1][0]+f[i][j−1][1]+(j>limit?mod−f[i][j−limit−1][0]:0))%mod
(3) 最终结果值为
(
f
[
zero
]
[
one
]
[
0
]
+
f
[
zero
]
[
one
]
[
1
]
)
%
mod
\left( f[\text{zero}][\text{one}][0] + f[\text{zero}][\text{one}][1] \right) \% \text{mod}
(f[zero][one][0]+f[zero][one][1])%mod
3. 代码实现
const long long mod = 1000000007;
class Solution {
public:
int numberOfStableArrays(int zero, int one, int limit) {
// f[i][j][k]表示i个0、j个1且当前位i+j填写值为k=0/1
vector<vector<vector<long long>>> f(
zero + 1, vector<vector<long long>>(one + 1, vector<long long>(2)));
// 连续limit+1个数字中不能只含有0或1,即至多有连续limit个0/1
for (int i = 1; i <= min(zero, limit); i++) {
f[i][0][0] = 1;
}
for (int j = 1; j <= min(one, limit); j++) {
f[0][j][1] = 1;
}
for (int i = 1; i <= zero; i++) {
for (int j = 1; j <= one; j++) {
// 减去包含的不合法方案
f[i][j][0] = (f[i - 1][j][0] + f[i - 1][j][1] +
(i > limit ? mod - f[i - limit - 1][j][1] : 0)) %
mod;
f[i][j][1] = (f[i][j - 1][0] + f[i][j - 1][1] +
(j > limit ? mod - f[i][j - limit - 1][0] : 0)) %
mod;
}
}
return (f[zero][one][0] + f[zero][one][1]) % mod;
}
};