LeetCode 3130.找出所有稳定的二进制数组 II动态规划 滑动窗口优化题目描述给定两个整数zero和one分别表示二进制数组中 0 和 1 的个数。你需要构造一个长度为zero one的二进制数组满足以下条件数组中恰好有zero个 0 和one个 1。任意相邻相同数字的连续长度不超过limit。求满足条件的数组个数结果对10^9 7取模。思路分析这是一道典型的计数类动态规划问题。直观的想法是按顺序构造数组记录已使用的 0 和 1 的个数以及最后一个数字是什么并确保最后一段连续相同的长度不超过限制。状态定义设f[i][j][k]表示已经使用了i个 0 和j个 1且数组最后一个数字是kk 0表示末尾为 0k 1表示末尾为 1的稳定数组个数。递推关系如果最后一个数字是 0那么最后一段连续的 0 的长度可以是 1 到limit。设这段连续 0 的长度为t则前一个状态必须是以 1 结尾且使用了i - t个 0 和j个 1。因此[f[i][j][0] \sum_{t1}^{\min(limit, i)} f[i-t][j][1]]如果最后一个数字是 1类似地[f[i][j][1] \sum_{t1}^{\min(limit, j)} f[i][j-t][0]]边界条件当j 0时数组全部由 0 组成必须满足i ≤ limit才有一种方案即所有 0 连在一起长度不超过限制且不可能以 1 结尾。故[f[i][0][0] (i \le limit) \quad\text{1 表示真0 表示假},\quad f[i][0][1] 0]当i 0时数组全部由 1 组成类似地[f[0][j][0] 0,\quad f[0][j][1] (j \le limit)]直接计算的复杂度如果按照上述递推式直接计算对于每个(i, j)都需要枚举t总复杂度为O(zero·one·limit)。当zero和one都较大时例如10^3以上可能会超时。因此需要优化。优化方法滑动窗口注意到递推式中的求和是连续一段的和我们可以利用滑动窗口或前缀和在 O(1) 时间内完成计算。定义两个辅助变量sum0对于固定的i随着j递增它维护了f[i][j-1][0] f[i][j-2][0] ... f[i][j-limit][0]的和即最近limit个f[i][*][0]的和。sum1[j]对于每个固定的j它维护了f[i-1][j][1] f[i-2][j][1] ... f[i-limit][j][1]的和即最近limit个f[*][j][1]的和。这样在计算f[i][j][0]时它恰好等于当前的sum1[j]计算f[i][j][1]时它恰好等于当前的sum0。更新策略计算完f[i][j][0]后将其加入sum0并移除超出窗口左边界的f[i][j-limit][0]如果存在。计算完f[i][j][1]后将其加入sum1[j]并移除超出窗口上边界的f[i-limit][j][1]如果存在。通过这样的维护每次计算只需要常数时间。代码实现intf[1005][1005][2]{0};// 全局数组假设 zero, one ≤ 1000classSolution{public:intnumberOfStableArrays(intzero,intone,intlimit){constintmod1e97;// 初始化边界条件for(inti0;izero;i){f[i][0][0](ilimit);// 全 0 数组只有 i ≤ limit 才合法f[i][0][1]0;}for(intj0;jone;j){f[0][j][0]0;f[0][j][1](jlimit);// 全 1 数组只有 j ≤ limit 才合法}// sum1[j] 用于维护 f[*][j][1] 的滑动窗口intsum1[one1];for(intj0;jone;j)sum1[j]f[0][j][1];// 主循环for(inti1;izero;i){// sum0 用于维护 f[i][*][0] 的滑动窗口初始为 f[i][0][0]for(intj1,sum0f[i][0][0];jone;j){// 计算 f[i][j][0] 和 f[i][j][1]f[i][j][0]sum1[j];f[i][j][1]sum0;// 更新 sum0为下一个 j1 准备sum0(sum0f[i][j][0])%mod;if(j-limit0)sum0(sum0mod-f[i][j-limit][0])%mod;// 更新 sum1[j]为下一个 i1 准备sum1[j](sum1[j]f[i][j][1])%mod;if(i-limit0)sum1[j](sum1[j]mod-f[i-limit][j][1])%mod;}}// 最终答案 以 0 结尾 以 1 结尾return(f[zero][one][0]f[zero][one][1])%mod;}};代码解释初始化分别处理全 0 和全 1 的边界情况。滑动窗口数组sum1初始时只有i 0一行所以sum1[j]即为f[0][j][1]。外层循环枚举已使用的 0 的个数i。内层循环枚举已使用的 1 的个数j并维护两个滑动窗口sum0随着j递增而动态变化用于计算f[i][j][1]。sum1[j]随着i递增而动态变化用于计算f[i][j][0]。更新细节每次加入新值后若窗口长度超过limit则减去窗口最左边的值注意取模处理减法。复杂度分析时间复杂度双重循环遍历所有(i, j)每次循环内部为 O(1) 操作总时间复杂度 O(zero·one)。空间复杂度使用了大小为(zero1)*(one1)*2的 DP 数组以及长度为one1的辅助数组空间复杂度 O(zero·one)。若空间紧张可以滚动数组优化但本题范围较小直接使用即可。与 LeetCode 3129 的区别LeetCode 3129 是“找出所有稳定的二进制数组 I”LeetCode 3130 是“找出所有稳定的二进制数组 II”。两者的题目描述完全相同唯一的区别在于数据范围3129 (I)数据范围较小通常允许使用 O(zero·one·limit) 的三重循环动态规划即直接对每个状态枚举最后一段的长度。3130 (II)数据范围较大必须采用优化方法如本文介绍的滑动窗口或前缀和将时间复杂度降至 O(zero·one)避免超时。因此本题的解法是 3129 的进阶版本体现了动态规划的优化技巧。总结本题的核心是状态定义与滑动窗口优化。通过维护两个滑动窗口我们将原本需要枚举长度的过程转化为 O(1) 查询从而高效地解决了大规模数据下的计数问题。这种技巧在类似的 DP 问题中非常常见值得熟练掌握。
LeetCode 3130.找出所有稳定的二进制数组 II
LeetCode 3130.找出所有稳定的二进制数组 II动态规划 滑动窗口优化题目描述给定两个整数zero和one分别表示二进制数组中 0 和 1 的个数。你需要构造一个长度为zero one的二进制数组满足以下条件数组中恰好有zero个 0 和one个 1。任意相邻相同数字的连续长度不超过limit。求满足条件的数组个数结果对10^9 7取模。思路分析这是一道典型的计数类动态规划问题。直观的想法是按顺序构造数组记录已使用的 0 和 1 的个数以及最后一个数字是什么并确保最后一段连续相同的长度不超过限制。状态定义设f[i][j][k]表示已经使用了i个 0 和j个 1且数组最后一个数字是kk 0表示末尾为 0k 1表示末尾为 1的稳定数组个数。递推关系如果最后一个数字是 0那么最后一段连续的 0 的长度可以是 1 到limit。设这段连续 0 的长度为t则前一个状态必须是以 1 结尾且使用了i - t个 0 和j个 1。因此[f[i][j][0] \sum_{t1}^{\min(limit, i)} f[i-t][j][1]]如果最后一个数字是 1类似地[f[i][j][1] \sum_{t1}^{\min(limit, j)} f[i][j-t][0]]边界条件当j 0时数组全部由 0 组成必须满足i ≤ limit才有一种方案即所有 0 连在一起长度不超过限制且不可能以 1 结尾。故[f[i][0][0] (i \le limit) \quad\text{1 表示真0 表示假},\quad f[i][0][1] 0]当i 0时数组全部由 1 组成类似地[f[0][j][0] 0,\quad f[0][j][1] (j \le limit)]直接计算的复杂度如果按照上述递推式直接计算对于每个(i, j)都需要枚举t总复杂度为O(zero·one·limit)。当zero和one都较大时例如10^3以上可能会超时。因此需要优化。优化方法滑动窗口注意到递推式中的求和是连续一段的和我们可以利用滑动窗口或前缀和在 O(1) 时间内完成计算。定义两个辅助变量sum0对于固定的i随着j递增它维护了f[i][j-1][0] f[i][j-2][0] ... f[i][j-limit][0]的和即最近limit个f[i][*][0]的和。sum1[j]对于每个固定的j它维护了f[i-1][j][1] f[i-2][j][1] ... f[i-limit][j][1]的和即最近limit个f[*][j][1]的和。这样在计算f[i][j][0]时它恰好等于当前的sum1[j]计算f[i][j][1]时它恰好等于当前的sum0。更新策略计算完f[i][j][0]后将其加入sum0并移除超出窗口左边界的f[i][j-limit][0]如果存在。计算完f[i][j][1]后将其加入sum1[j]并移除超出窗口上边界的f[i-limit][j][1]如果存在。通过这样的维护每次计算只需要常数时间。代码实现intf[1005][1005][2]{0};// 全局数组假设 zero, one ≤ 1000classSolution{public:intnumberOfStableArrays(intzero,intone,intlimit){constintmod1e97;// 初始化边界条件for(inti0;izero;i){f[i][0][0](ilimit);// 全 0 数组只有 i ≤ limit 才合法f[i][0][1]0;}for(intj0;jone;j){f[0][j][0]0;f[0][j][1](jlimit);// 全 1 数组只有 j ≤ limit 才合法}// sum1[j] 用于维护 f[*][j][1] 的滑动窗口intsum1[one1];for(intj0;jone;j)sum1[j]f[0][j][1];// 主循环for(inti1;izero;i){// sum0 用于维护 f[i][*][0] 的滑动窗口初始为 f[i][0][0]for(intj1,sum0f[i][0][0];jone;j){// 计算 f[i][j][0] 和 f[i][j][1]f[i][j][0]sum1[j];f[i][j][1]sum0;// 更新 sum0为下一个 j1 准备sum0(sum0f[i][j][0])%mod;if(j-limit0)sum0(sum0mod-f[i][j-limit][0])%mod;// 更新 sum1[j]为下一个 i1 准备sum1[j](sum1[j]f[i][j][1])%mod;if(i-limit0)sum1[j](sum1[j]mod-f[i-limit][j][1])%mod;}}// 最终答案 以 0 结尾 以 1 结尾return(f[zero][one][0]f[zero][one][1])%mod;}};代码解释初始化分别处理全 0 和全 1 的边界情况。滑动窗口数组sum1初始时只有i 0一行所以sum1[j]即为f[0][j][1]。外层循环枚举已使用的 0 的个数i。内层循环枚举已使用的 1 的个数j并维护两个滑动窗口sum0随着j递增而动态变化用于计算f[i][j][1]。sum1[j]随着i递增而动态变化用于计算f[i][j][0]。更新细节每次加入新值后若窗口长度超过limit则减去窗口最左边的值注意取模处理减法。复杂度分析时间复杂度双重循环遍历所有(i, j)每次循环内部为 O(1) 操作总时间复杂度 O(zero·one)。空间复杂度使用了大小为(zero1)*(one1)*2的 DP 数组以及长度为one1的辅助数组空间复杂度 O(zero·one)。若空间紧张可以滚动数组优化但本题范围较小直接使用即可。与 LeetCode 3129 的区别LeetCode 3129 是“找出所有稳定的二进制数组 I”LeetCode 3130 是“找出所有稳定的二进制数组 II”。两者的题目描述完全相同唯一的区别在于数据范围3129 (I)数据范围较小通常允许使用 O(zero·one·limit) 的三重循环动态规划即直接对每个状态枚举最后一段的长度。3130 (II)数据范围较大必须采用优化方法如本文介绍的滑动窗口或前缀和将时间复杂度降至 O(zero·one)避免超时。因此本题的解法是 3129 的进阶版本体现了动态规划的优化技巧。总结本题的核心是状态定义与滑动窗口优化。通过维护两个滑动窗口我们将原本需要枚举长度的过程转化为 O(1) 查询从而高效地解决了大规模数据下的计数问题。这种技巧在类似的 DP 问题中非常常见值得熟练掌握。
