3129. 寻找所有可能的稳定二进制数组 I

Medium

题目描述

给你 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]，因为这两个数组都有一个 0 和一个 1，且没有长度大于 2 的子数组。

示例 2：

输入：zero = 1, one = 2, limit = 1
输出：1
解释：唯一可能的稳定二进制数组是 [1,0,1]。
注意二进制数组 [1,1,0] 和 [0,1,1] 有长度为 2 的相同元素子数组，因此它们不稳定。

示例 3：

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

约束条件：

1 <= zero, one, limit <= 200

解题思路

这是一个动态规划问题。核心思路是定义状态来追踪当前已经使用的 0 和 1 的个数，以及数组末尾连续相同字符的情况。

状态定义： 设 dp[i][j][last][cnt] 表示使用了 i 个 0 和 j 个 1，且末尾连续 cnt 个字符 last（0 或 1）的稳定数组个数。

状态转移：

如果在末尾添加一个 0：
- 如果之前末尾是 1，那么连续 0 的个数重置为 1
- 如果之前末尾是 0，那么连续 0 的个数加 1，但不能超过 limit
如果在末尾添加一个 1：
- 如果之前末尾是 0，那么连续 1 的个数重置为 1
- 如果之前末尾是 1，那么连续 1 的个数加 1，但不能超过 limit

边界条件： 初始状态 dp[1][0][0][1] = 1（一个 0）和 dp[0][1][1][1] = 1（一个 1）。

优化： 可以使用前缀和优化转移过程，避免重复计算相同末尾字符但不同连续长度的状态和。

最终答案是所有满足条件的 dp[zero][one][last][cnt] 的总和。

代码实现

class Solution {
public:
    int numberOfStableArrays(int zero, int one, int limit) {
        const int MOD = 1e9 + 7;
        
        // dp[i][j][last][cnt] = number of ways with i zeros, j ones, 
        // ending with 'last' (0 or 1) with cnt consecutive same characters
        int dp[201][201][2][201];
        memset(dp, 0, sizeof(dp));
        
        // Base cases
        if (zero > 0) dp[1][0][0][1] = 1;
        if (one > 0) dp[0][1][1][1] = 1;
        
        for (int i = 0; i <= zero; i++) {
            for (int j = 0; j <= one; j++) {
                if (i == 0 && j == 0) continue;
                
                // Add a 0
                if (i > 0) {
                    // From ending with 1 to ending with 0
                    for (int cnt = 1; cnt <= limit && cnt <= j; cnt++) {
                        dp[i][j][0][1] = (dp[i][j][0][1] + dp[i-1][j][1][cnt]) % MOD;
                    }
                    // From ending with 0 to ending with 0
                    for (int cnt = 1; cnt < limit && cnt < i; cnt++) {
                        dp[i][j][0][cnt+1] = (dp[i][j][0][cnt+1] + dp[i-1][j][0][cnt]) % MOD;
                    }
                }
                
                // Add a 1
                if (j > 0) {
                    // From ending with 0 to ending with 1
                    for (int cnt = 1; cnt <= limit && cnt <= i; cnt++) {
                        dp[i][j][1][1] = (dp[i][j][1][1] + dp[i][j-1][0][cnt]) % MOD;
                    }
                    // From ending with 1 to ending with 1
                    for (int cnt = 1; cnt < limit && cnt < j; cnt++) {
                        dp[i][j][1][cnt+1] = (dp[i][j][1][cnt+1] + dp[i][j-1][1][cnt]) % MOD;
                    }
                }
            }
        }
        
        int result = 0;
        for (int cnt = 1; cnt <= limit; cnt++) {
            result = (result + dp[zero][one][0][cnt]) % MOD;
            result = (result + dp[zero][one][1][cnt]) % MOD;
        }
        
        return result;
    }
};

class Solution:
    def numberOfStableArrays(self, zero: int, one: int, limit: int) -> int:
        MOD = 10**9 + 7
        
        # dp[i][j][last][cnt] = number of ways with i zeros, j ones,
        # ending with 'last' (0 or 1) with cnt consecutive same characters
        dp = [[[[0 for _ in range(limit + 1)] for _ in range(2)] for _ in range(one + 1)] for _ in range(zero + 1)]
        
        # Base cases
        if zero > 0:
            dp[1][0][0][1] = 1
        if one > 0:
            dp[0][1][1][1] = 1
        
        for i in range(zero + 1):
            for j in range(one + 1):
                if i == 0 and j == 0:
                    continue
                
                # Add a 0
                if i > 0:
                    # From ending with 1 to ending with 0
                    for cnt in range(1, min(limit + 1, j + 1)):
                        dp[i][j][0][1] = (dp[i][j][0][1] + dp[i-1][j][1][cnt]) % MOD
                    # From ending with 0 to ending with 0
                    for cnt in range(1, min(limit, i)):
                        dp[i][j][0][cnt+1] = (dp[i][j][0][cnt+1] + dp[i-1][j][0][cnt]) % MOD
                
                # Add a 1
                if j > 0:
                    # From ending with 0 to ending with 1
                    for cnt in range(1, min(limit + 1, i + 1)):
                        dp[i][j][1][1] = (dp[i][j][1][1] + dp[i][j-1][0][cnt]) % MOD
                    # From ending with 1 to ending with 1
                    for cnt in range(1, min(limit, j)):
                        dp[i][j][1][cnt+1] = (dp[i][j][1][cnt+1] + dp[i][j-1][1][cnt]) % MOD
        
        result = 0
        for cnt in range(1, limit + 1):
            result = (result + dp[zero][one][0][cnt]) % MOD
            result = (result + dp[zero][one][1][cnt]) % MOD
        
        return result

public class Solution {
    public int NumberOfStableArrays(int zero, int one, int limit) {
        const int MOD = 1000000007;
        
        // dp[i,j,last,cnt] = number of ways with i zeros, j ones,
        // ending with 'last' (0 or 1) with cnt consecutive same characters
        int[,,,] dp = new int[zero + 1, one + 1, 2, limit + 1];
        
        // Base cases
        if (zero > 0) dp[1, 0, 0, 1] = 1;
        if (one > 0) dp[0, 1, 1, 1] = 1;
        
        for (int i = 0; i <= zero; i++) {
            for (int j = 0; j <= one; j++) {
                if (i == 0 && j == 0) continue;
                
                // Add a 0
                if (i > 0) {
                    // From ending with 1 to ending with 0
                    for (int cnt = 1; cnt <= Math.Min(limit, j); cnt++) {
                        dp[i, j, 0, 1] = (dp[i, j, 0, 1] + dp[i - 1, j, 1, cnt]) % MOD;
                    }
                    // From ending with 0 to ending with 0
                    for (int cnt = 1; cnt < Math.Min(limit, i); cnt++) {
                        dp[i, j, 0, cnt + 1] = (dp[i, j, 0, cnt + 1] + dp[i - 1, j, 0, cnt]) % MOD;
                    }
                }
                
                // Add a 1
                if (j > 0) {
                    // From ending with 0 to ending with 1
                    for (int cnt = 1; cnt <= Math.Min(limit, i); cnt++) {
                        dp[i, j, 1, 1] = (dp[i, j, 1, 1] + dp[i, j - 1, 0, cnt]) % MOD;
                    }
                    // From ending with 1 to ending with 1
                    for (int cnt = 1; cnt < Math.Min(limit, j); cnt++) {
                        dp[i, j, 1, cnt + 1] = (dp[i, j, 1, cnt + 1] + dp[i, j - 1, 1, cnt]) % MOD;
                    }
                }
            }
        }
        
        int result = 0;
        for (int cnt = 1; cnt <= limit; cnt++) {
            result = (result + dp[zero, one, 0, cnt]) % MOD;
            result = (result + dp[zero, one, 1, cnt]) % MOD;
        }
        
        return result;
    }
}

var numberOfStableArrays = function(zero, one, limit) {
    const MOD = 1000000007;
    const memo = new Map();
    
    function dp(z, o, last, count) {
        if (z < 0 || o < 0 || count > limit) return 0;
        if (z === 0 && o === 0) return 1;
        
        const key = `${z},${o},${last},${count}`;
        if (memo.has(key)) return memo.get(key);
        
        let result = 0;
        
        if (z > 0) {
            if (last === 0) {
                result = (result + dp(z - 1, o, 0, count + 1)) % MOD;
            } else {
                result = (result + dp(z - 1, o, 0, 1)) % MOD;
            }
        }
        
        if (o > 0) {
            if (last === 1) {
                result = (result + dp(z, o - 1, 1, count + 1)) % MOD;
            } else {
                result = (result + dp(z, o - 1, 1, 1)) % MOD;
            }
        }
        
        memo.set(key, result);
        return result;
    }
    
    return (dp(zero - 1, one, 0, 1) + dp(zero, one - 1, 1, 1)) % MOD;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	值
时间复杂度	O(zero × one × limit²)
空间复杂度	O(zero × one × limit)

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目