问题描述给定 3 个正整数 zero、one 和 limit要求计算满足以下条件的稳定二进制数组总数数组中 0 出现次数恰好为 zero数组中 1 出现次数恰好为 one数组中每个长度超过 limit 的子数组都同时包含 0 和 1等价于数组中连续的 0 或连续的 1 的长度都不超过 limit答案需要对109710^9 71097取余。解题思路核心思路这是一道典型的动态规划问题我们需要定义状态来表示构建数组过程中的关键信息状态定义dp[i][j][k]表示使用 i 个 0、j 个 1且最后一个元素是 k0 或 1的稳定数组数量状态转移当最后一个元素是 0 时需要考虑前面可以连续放多少个 01~limit 个当最后一个元素是 1 时同理需要考虑前面可以连续放多少个 11~limit 个具体步骤初始化边界条件当只有 0 或只有 1 且数量不超过 limit 时的情况状态转移计算以 0 结尾的情况dp[i][j][0] sum(dp[i-t][j][1])其中 t 从 1 到 min(limit, i)计算以 1 结尾的情况dp[i][j][1] sum(dp[i][j-t][0])其中 t 从 1 到 min(limit, j)最终结果(dp[zero][one][0] dp[zero][one][1]) % MOD完整代码实现class Solution: def numberOfStableArrays(self, zero: int, one: int, limit: int) - int: MOD 10**9 7 # 初始化DP数组dp[i][j][0/1] 表示i个0j个1最后一位是0/1的稳定数组数量 # 使用三维列表维度为 (zero1) x (one1) x 2 dp [[[0] * 2 for _ in range(one 1)] for __ in range(zero 1)] # 边界条件1只有0的情况j0 for i in range(1, min(limit, zero) 1): dp[i][0][0] 1 # 边界条件2只有1的情况i0 for j in range(1, min(limit, one) 1): dp[0][j][1] 1 # 动态规划状态转移 for i in range(zero 1): for j in range(one 1): # 跳过边界条件的情况 if i 0 or j 0: continue # 计算以0结尾的情况最后连续t个0t从1到limit # 前面必须是以1结尾且用了i-t个0j个1 max_t0 min(limit, i) for t in range(1, max_t0 1): dp[i][j][0] (dp[i][j][0] dp[i - t][j][1]) % MOD # 计算以1结尾的情况最后连续t个1t从1到limit # 前面必须是以0结尾且用了i个0j-t个1 max_t1 min(limit, j) for t in range(1, max_t1 1): dp[i][j][1] (dp[i][j][1] dp[i][j - t][0]) % MOD # 最终结果是两种结尾情况的和 return (dp[zero][one][0] dp[zero][one][1]) % MOD代码优化前缀和优化上述基础解法的时间复杂度为O(zero×one×limit)O(zero \times one \times limit)O(zero×one×limit)对于题目给定的约束zero, one ≤ 200已经足够。如果需要进一步优化可以使用前缀和将时间复杂度降为O(zero×one)O(zero \times one)O(zero×one)class Solution: def numberOfStableArrays(self, zero: int, one: int, limit: int) - int: MOD 10**9 7 # DP数组定义同上 dp [[[0] * 2 for _ in range(one 1)] for __ in range(zero 1)] # 前缀和数组pre0[i][j] 表示以1结尾的i个0、j个1的前缀和 # pre1[i][j] 表示以0结尾的i个0、j个1的前缀和 pre0 [[0] * (one 1) for __ in range(zero 1)] pre1 [[0] * (one 1) for __ in range(zero 1)] # 初始化 for i in range(1, min(limit, zero) 1): dp[i][0][0] 1 for j in range(1, min(limit, one) 1): dp[0][j][1] 1 # 动态规划 前缀和优化 for i in range(zero 1): for j in range(one 1): if i 0 and j 0: continue # 计算以0结尾的情况 if j 0: left max(0, i - limit) dp[i][j][0] (pre0[i-1][j] - (pre0[left-1][j] if left 0 else 0)) % MOD # 计算以1结尾的情况 if i 0: left max(0, j - limit) dp[i][j][1] (pre1[i][j-1] - (pre1[i][left-1] if left 0 else 0)) % MOD # 更新前缀和 pre0[i][j] (pre0[i-1][j] dp[i][j][1]) % MOD if i 0 else dp[i][j][1] pre1[i][j] (pre1[i][j-1] dp[i][j][0]) % MOD if j 0 else dp[i][j][0] return (dp[zero][one][0] dp[zero][one][1]) % MOD代码解析基础版本解析DP数组初始化创建三维数组dp[zero1][one1][2]分别表示0的数量、1的数量、最后一位的类型初始化只有0或只有1的边界情况当数量不超过limit时对应的dp值为1状态转移遍历所有可能的0和1的数量组合对于以0结尾的情况累加前面放1个、2个…最多limit个0的情况且前面必须是以1结尾对于以1结尾的情况同理累加前面放1个到limit个1的情况且前面必须是以0结尾结果计算将以0结尾和以1结尾的情况相加取模得到最终结果优化版本解析使用前缀和数组pre0和pre1来存储累计和避免每次都循环计算sumpre0[i][j]存储以1结尾的i个0、j个1的前缀和pre1[i][j]存储以0结尾的i个0、j个1的前缀和通过前缀和的差值快速计算连续limit个的和将时间复杂度从O(zero×one×limit)优化到O(zero×one)示例验证示例1输入zero1, one1, limit2dp[1][1][0] dp[0][1][1] 1dp[1][1][1] dp[1][0][0] 1结果112 ✔️示例2输入zero1, one2, limit1dp[1][2][0] dp[0][2][1] 0因为2limit1dp[1][2][1] dp[1][1][0] 1结果011 ✔️示例3输入zero3, one3, limit2最终计算结果为14 ✔️复杂度分析时间复杂度基础版本O(zero×one×limit)O(zero \times one \times limit)O(zero×one×limit)优化版本O(zero×one)O(zero \times one)O(zero×one)空间复杂度O(zero×one)O(zero \times one)O(zero×one)三维DP数组总结本题的核心是动态规划通过定义状态dp[i][j][k]来记录构建过程中的关键信息其中k表示最后一位的类型状态转移的关键是保证连续的0或1不超过limit个需要累加前面1~limit个连续相同数字的情况可以通过前缀和优化将时间复杂度从O(zero×one×limit)O(zero \times one \times limit)O(zero×one×limit)降为O(zero×one)O(zero \times one)O(zero×one)提升算法效率该解法能够有效处理题目给定的约束条件zero, one ≤ 200并且通过取模操作避免数值溢出符合题目要求。