这道题是 LeetCode 第 129 场双周赛的 T4难度分 2825属于比较难的动态规划题。核心思路是使用 三维动态规划 配合 容斥原理 来优化状态转移。思路解析状态定义dp[i][j][k] 表示使用了 i 个 0 和 j 个 1且最后一个数字为 k0 或 1的稳定二进制数组数量。转移方程- dp[i][j][0]最后一个放 0可以由之前放 0 或放 1 的状态转移而来。但如果连续 0 超过 limit需要减去不合法的情况。- dp[i][j][1]同理最后一个放 1。具体转移以 dp[i][j][0] 为例- 所有以 0 结尾的方案 在 i-1 个 0 和 j 个 1 的合法数组末尾加 0- 不合法的情况是之前末尾已经有 limit 个连续 0再加一个 0 就超过 limit- 所以需要减去 dp[i-limit-1][j][1]即末尾是 1前面刚好有 limit 个 0 连续的情况边界条件- dp[i][0][0] 1当 i limit 时全 0 数组是合法的- dp[0][j][1] 1当 j limit 时全 1 数组是合法的Java 实现javaclass Solution {public int numberOfStableArrays(int zero, int one, int limit) {final int MOD 1_000_000_007;// dp[i][j][k]: 使用 i 个 0 和 j 个 1最后一个数字为 k 的稳定数组数量// k 0 表示最后一个数字是 0k 1 表示最后一个数字是 1long[][][] dp new long[zero 1][one 1][2];// 初始化只有 0 的情况i 个 00 个 1以 0 结尾// 当 i limit 时全 0 数组是稳定的for (int i 1; i Math.min(zero, limit); i) {dp[i][0][0] 1;}// 初始化只有 1 的情况0 个 0j 个 1以 1 结尾// 当 j limit 时全 1 数组是稳定的for (int j 1; j Math.min(one, limit); j) {dp[0][j][1] 1;}// 动态规划填表for (int i 1; i zero; i) {for (int j 1; j one; j) {// 计算 dp[i][j][0]最后一个放 0// 可以由 dp[i-1][j][0] 和 dp[i-1][j][1] 转移而来dp[i][j][0] (dp[i - 1][j][0] dp[i - 1][j][1]) % MOD;// 减去不合法的情况连续 0 超过 limit// 即前面已经有 limit 个连续 0此时末尾是 1再改成 0 就不合法if (i limit) {dp[i][j][0] (dp[i][j][0] - dp[i - limit - 1][j][1] MOD) % MOD;}// 计算 dp[i][j][1]最后一个放 1// 可以由 dp[i][j-1][0] 和 dp[i][j-1][1] 转移而来dp[i][j][1] (dp[i][j - 1][0] dp[i][j - 1][1]) % MOD;// 减去不合法的情况连续 1 超过 limitif (j limit) {dp[i][j][1] (dp[i][j][1] - dp[i][j - limit - 1][0] MOD) % MOD;}}}// 最终答案使用 zero 个 0 和 one 个 1最后一个可以是 0 或 1return (int) ((dp[zero][one][0] dp[zero][one][1]) % MOD);}}关键点说明1. 容斥原理dp[i][j][0] (dp[i-1][j][0] dp[i-1][j][1]) - dp[i-limit-1][j][1]- 前两项是所有在末尾加 0 的方案- 第三项是减去那些会导致连续 0 超过 limit 的不合法方案2. 防止负数每次减法后都要 MOD 再 % MOD因为 Java 中负数取模结果仍为负数。3. 时间复杂度O(zero × one)空间复杂度O(zero × one)。对于 zero, one, limit 1000 的数据范围完全可以通过。4. 与 3129 题的关系这道题和 3129Find All Possible Stable Binary Arrays I解法完全相同只是数据范围更大要求更高的实现效率。示例验证- zero1, one1, limit2输出 2[0,1] 和 [1,0]- zero1, one2, limit1输出 1只有 [1,0,1]- zero3, one3, limit2输出 14
Kimi LeetCode 3130. 找出所有稳定的二进制数组 II Java实现
这道题是 LeetCode 第 129 场双周赛的 T4难度分 2825属于比较难的动态规划题。核心思路是使用 三维动态规划 配合 容斥原理 来优化状态转移。思路解析状态定义dp[i][j][k] 表示使用了 i 个 0 和 j 个 1且最后一个数字为 k0 或 1的稳定二进制数组数量。转移方程- dp[i][j][0]最后一个放 0可以由之前放 0 或放 1 的状态转移而来。但如果连续 0 超过 limit需要减去不合法的情况。- dp[i][j][1]同理最后一个放 1。具体转移以 dp[i][j][0] 为例- 所有以 0 结尾的方案 在 i-1 个 0 和 j 个 1 的合法数组末尾加 0- 不合法的情况是之前末尾已经有 limit 个连续 0再加一个 0 就超过 limit- 所以需要减去 dp[i-limit-1][j][1]即末尾是 1前面刚好有 limit 个 0 连续的情况边界条件- dp[i][0][0] 1当 i limit 时全 0 数组是合法的- dp[0][j][1] 1当 j limit 时全 1 数组是合法的Java 实现javaclass Solution {public int numberOfStableArrays(int zero, int one, int limit) {final int MOD 1_000_000_007;// dp[i][j][k]: 使用 i 个 0 和 j 个 1最后一个数字为 k 的稳定数组数量// k 0 表示最后一个数字是 0k 1 表示最后一个数字是 1long[][][] dp new long[zero 1][one 1][2];// 初始化只有 0 的情况i 个 00 个 1以 0 结尾// 当 i limit 时全 0 数组是稳定的for (int i 1; i Math.min(zero, limit); i) {dp[i][0][0] 1;}// 初始化只有 1 的情况0 个 0j 个 1以 1 结尾// 当 j limit 时全 1 数组是稳定的for (int j 1; j Math.min(one, limit); j) {dp[0][j][1] 1;}// 动态规划填表for (int i 1; i zero; i) {for (int j 1; j one; j) {// 计算 dp[i][j][0]最后一个放 0// 可以由 dp[i-1][j][0] 和 dp[i-1][j][1] 转移而来dp[i][j][0] (dp[i - 1][j][0] dp[i - 1][j][1]) % MOD;// 减去不合法的情况连续 0 超过 limit// 即前面已经有 limit 个连续 0此时末尾是 1再改成 0 就不合法if (i limit) {dp[i][j][0] (dp[i][j][0] - dp[i - limit - 1][j][1] MOD) % MOD;}// 计算 dp[i][j][1]最后一个放 1// 可以由 dp[i][j-1][0] 和 dp[i][j-1][1] 转移而来dp[i][j][1] (dp[i][j - 1][0] dp[i][j - 1][1]) % MOD;// 减去不合法的情况连续 1 超过 limitif (j limit) {dp[i][j][1] (dp[i][j][1] - dp[i][j - limit - 1][0] MOD) % MOD;}}}// 最终答案使用 zero 个 0 和 one 个 1最后一个可以是 0 或 1return (int) ((dp[zero][one][0] dp[zero][one][1]) % MOD);}}关键点说明1. 容斥原理dp[i][j][0] (dp[i-1][j][0] dp[i-1][j][1]) - dp[i-limit-1][j][1]- 前两项是所有在末尾加 0 的方案- 第三项是减去那些会导致连续 0 超过 limit 的不合法方案2. 防止负数每次减法后都要 MOD 再 % MOD因为 Java 中负数取模结果仍为负数。3. 时间复杂度O(zero × one)空间复杂度O(zero × one)。对于 zero, one, limit 1000 的数据范围完全可以通过。4. 与 3129 题的关系这道题和 3129Find All Possible Stable Binary Arrays I解法完全相同只是数据范围更大要求更高的实现效率。示例验证- zero1, one1, limit2输出 2[0,1] 和 [1,0]- zero1, one2, limit1输出 1只有 [1,0,1]- zero3, one3, limit2输出 14
