Hard

题目描述

给定3个正整数 zero、one 和 limit。

二进制数组 arr 被称为稳定的，如果：

  • arr 中 0 的出现次数恰好为 zero
  • arr 中 1 的出现次数恰好为 one
  • arr 中任何长度大于 limit 的子数组都必须同时包含 0 和 1

返回稳定二进制数组的总数。

由于答案可能很大，返回结果对 10^9 + 7 取模。

示例 1：

输入：zero = 1, one = 1, limit = 2
输出：2
解释：两个可能的稳定二进制数组是 [1,0] 和 [0,1]。

示例 2：

输入：zero = 1, one = 2, limit = 1
输出：1
解释：唯一可能的稳定二进制数组是 [1,0,1]。

示例 3：

输入：zero = 3, one = 3, limit = 2
输出：14

约束条件：

  • 1 <= zero, one, limit <= 1000

解题思路

这道题需要使用动态规划来解决。核心思想是定义状态 dp[i][j][k] 表示使用了 i 个0和 j 个1，且最后一个元素是 k（0或1）的稳定数组数量。

状态转移分析：

  1. 如果当前要放置一组连续的0，长度为 len（1 ≤ len ≤ limit），那么这组0之前必须是1
  2. 同样，如果要放置一组连续的1，这组1之前必须是0
  3. 状态转移方程：
    • dp[i][j][0] = sum(dp[i-len][j][1]) for len in [1, min(limit, i)]
    • dp[i][j][1] = sum(dp[i][j-len][0]) for len in [1, min(limit, j)]

优化技巧： 为了避免重复计算求和，使用前缀和数组来优化：

  • prefix0[i][j] = dp[0][j][0] + dp[1][j][0] + ... + dp[i][j][0]
  • prefix1[i][j] = dp[i][0][1] + dp[i][1][1] + ... + dp[i][j][1]

通过前缀和，可以在O(1)时间内计算出区间和，将整体复杂度从O(zero × one × limit)降低到O(zero × one)。

边界条件：

  • dp[0][j][1] = 1 当 1 ≤ j ≤ limit 时
  • dp[i][0][0] = 1 当 1 ≤ i ≤ limit 时

代码实现

class Solution {
public:
    int numberOfStableArrays(int zero, int one, int limit) {
        const int MOD = 1e9 + 7;
        vector<vector<vector<long long>>> dp(zero + 1, vector<vector<long long>>(one + 1, vector<long long>(2, 0)));
        vector<vector<long long>> prefix0(zero + 1, vector<long long>(one + 1, 0));
        vector<vector<long long>> prefix1(zero + 1, vector<long long>(one + 1, 0));
        
        // 初始化边界条件
        for (int j = 1; j <= min(one, limit); j++) {
            dp[0][j][1] = 1;
            prefix1[0][j] = prefix1[0][j-1] + 1;
        }
        for (int i = 1; i <= min(zero, limit); i++) {
            dp[i][0][0] = 1;
            prefix0[i][0] = prefix0[i-1][0] + 1;
        }
        
        for (int i = 1; i <= zero; i++) {
            for (int j = 1; j <= one; j++) {
                // 计算以0结尾的方案数
                int maxLen = min(limit, i);
                long long sum = prefix1[i-1][j] - (i-maxLen-1 >= 0 ? prefix1[i-maxLen-1][j] : 0);
                dp[i][j][0] = (sum % MOD + MOD) % MOD;
                
                // 计算以1结尾的方案数
                maxLen = min(limit, j);
                sum = prefix0[i][j-1] - (j-maxLen-1 >= 0 ? prefix0[i][j-maxLen-1] : 0);
                dp[i][j][1] = (sum % MOD + MOD) % MOD;
                
                // 更新前缀和
                prefix0[i][j] = (prefix0[i-1][j] + dp[i][j][0]) % MOD;
                prefix1[i][j] = (prefix1[i][j-1] + dp[i][j][1]) % MOD;
            }
        }
        
        return (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 = [[[0] * 2 for _ in range(one + 1)] for _ in range(zero + 1)]
        prefix0 = [[0] * (one + 1) for _ in range(zero + 1)]
        prefix1 = [[0] * (one + 1) for _ in range(zero + 1)]
        
        # 初始化边界条件
        for j in range(1, min(one, limit) + 1):
            dp[0][j][1] = 1
            prefix1[0][j] = prefix1[0][j-1] + 1
            
        for i in range(1, min(zero, limit) + 1):
            dp[i][0][0] = 1
            prefix0[i][0] = prefix0[i-1][0] + 1
        
        for i in range(1, zero + 1):
            for j in range(1, one + 1):
                # 计算以0结尾的方案数
                max_len = min(limit, i)
                sum_val = prefix1[i-1][j] - (prefix1[i-max_len-1][j] if i-max_len-1 >= 0 else 0)
                dp[i][j][0] = sum_val % MOD
                
                # 计算以1结尾的方案数
                max_len = min(limit, j)
                sum_val = prefix0[i][j-1] - (prefix0[i][j-max_len-1] if j-max_len-1 >= 0 else 0)
                dp[i][j][1] = sum_val % MOD
                
                # 更新前缀和
                prefix0[i][j] = (prefix0[i-1][j] + dp[i][j][0]) % MOD
                prefix1[i][j] = (prefix1[i][j-1] + dp[i][j][1]) % MOD
        
        return (dp[zero][one][0] + dp[zero][one][1]) % MOD

public class Solution {
    public int NumberOfStableArrays(int zero, int one, int limit) {
        const int MOD = 1000000007;
        long[,,] dp = new long[zero + 1, one + 1, 2];
        long[,] prefix0 = new long[zero + 1, one + 1];
        long[,] prefix1 = new long[zero + 1, one + 1];
        
        // 初始化边界条件
        for (int j = 1; j <= Math.Min(one, limit); j++) {
            dp[0, j, 1] = 1;
            prefix1[0, j] = prefix1[0, j-1] + 1;
        }
        for (int i = 1; i <= Math.Min(zero, limit); i++) {
            dp[i, 0, 0] = 1;
            prefix0[i, 0] = prefix0[i-1, 0] + 1;
        }
        
        for (int i = 1; i <= zero; i++) {
            for (int j = 1; j <= one; j++) {
                // 计算以0结尾的方案数
                int maxLen = Math.Min(limit, i);
                long sum = prefix1[i-1, j] - (i-maxLen-1 >= 0 ? prefix1[i-maxLen-1, j] : 0);
                dp[i, j, 0] = ((sum % MOD) + MOD) % MOD;
                
                // 计算以1结尾的方案数
                maxLen = Math.Min(limit, j);
                sum = prefix0[i, j-1] - (j-maxLen-1 >= 0 ? prefix0[i, j-maxLen-1] : 0);
                dp[i, j, 1] = ((sum % MOD) + MOD) % MOD;
                
                // 更新前缀和
                prefix0[i, j] = (prefix0[i-1, j] + dp[i, j, 0]) % MOD;
                prefix1[i, j] = (prefix1[i, j-1] + dp[i, j, 1]) % MOD;
            }
        }
        
        return (int)((dp[zero, one, 0] + dp[zero, one, 1]) % MOD);
    }
}

var numberOfStableArrays = function(zero, one, limit) {
    const MOD = 1e9 + 7;
    const dp = Array(zero + 1).fill().map(() => 
        Array(one + 1).fill().map(() => [0, 0])
    );
    const prefix0 = Array(zero + 1).fill().map(() => Array(one + 1).fill(0));
    const prefix1 = Array(zero + 1).fill().map(() => Array(one + 1).fill(0));
    
    // 初始化边界条件
    for (let j = 1; j <= Math.min(one, limit); j++) {
        dp[0][j][1] = 1;
        prefix1[0][j] = prefix1[0][j-1] + 1;
    }
    for (let i = 1; i <= Math.min(zero, limit); i++) {
        dp[i][0][0] = 1;
        prefix0[i][0] = prefix0[i-1][0] + 1;
    }
    
    for (let i = 1; i <= zero; i++) {
        for (let j = 1; j <= one; j++) {
            // 计算以0结尾的方案数
            let maxLen = Math.min(limit, i);
            let sum = prefix1[i-1][j] - (i-maxLen-1 >= 0 ? prefix1[i-maxLen-1][j] : 0);
            dp[i][j][0] = ((sum % MOD) + MOD) % MOD;
            
            // 计算以1结尾的方案数
            maxLen = Math.min(limit, j);
            sum = prefix0[i][j-1] - (j-maxLen-1 >= 0 ? prefix0[i][j-maxLen-1] : 0);
            dp[i][j][1] = ((sum % MOD) + MOD) % MOD;
            
            // 更新前缀和
            prefix0[i][j] = (prefix0[i-1][j] + dp[i][j][0]) % MOD;
            prefix1[i][j] = (prefix1[i][j-1] + dp[i][j][1]) % MOD;
        }
    }
    
    return (dp[zero][one][0] + dp[zero][one][1]) % MOD;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(zero × one)
空间复杂度O(zero × one)

通过前缀和优化，避免了内层的limit循环，使时间复杂度从O(zero × one × limit)降低到O(zero × one)。空间复杂度主要由dp数组和前缀和数组决定。

相关题目