当前位置：首页 > article >正文

算法求解 -- (炼码 3854 题)计算满足条件的好二进制字符串数量

article 2024/11/15 3:40:43

文章目录

1. 问题描述(炼码 3854 题)
2. 解决方案概述
3. 动态规划详解
4. 代码实现
5. 示例解析
6. 总结

1. 问题描述(炼码 3854 题)

给定四个正整数 minLength、maxLength、zeroGroup 和 oneGroup。需要找到所有的好二进制字符串，一个好二进制字符串需要满足以下条件：

字符串长度在 [minLength, maxLength] 之间。
对于字符串中的每块连续 0 的子串，其长度必须是 zeroGroup 的整数倍。
对于字符串中的每块连续 1 的子串，其长度必须是 oneGroup 的整数倍。
0 被认为是所有数字的整数倍，即对于 zeroGroup = 2，oneGroup = 3，字符串 “00” 和 “111” 可以被认为是一个好二进制字符串。

返回满足条件的好二进制字符串的数量，答案可能很大，返回对10的9次方+7取余后的结果。

2. 解决方案概述

为了高效地解决这个问题，我们可以使用动态规划。定义 dp[i] 表示长度为 i 的好二进制字符串的数量。通过状态转移方程，我们可以逐步计算出所有满足条件的字符串数量。

3. 动态规划详解

状态定义

dp[i]：表示长度为 i 的好二进制字符串的数量。

状态转移方程

如果在长度为 i 的字符串末尾添加 zeroGroup 个 0，则新字符串的长度为 i + zeroGroup，并且必须满足 i + zeroGroup 在 [minLength, maxLength] 范围内。
如果在长度为 i 的字符串末尾添加 oneGroup 个 1，则新字符串的长度为 i + oneGroup，并且必须满足 i + oneGroup 在 [minLength, maxLength] 范围内。

初始化

dp[0] = 1：表示空字符串是一种有效的初始状态。

结果计算

遍历所有在 [minLength, maxLength] 范围内的长度，累加对应的 dp 值。

4. 代码实现

using System;

public class Solution {
    public int CountGoodBinaryStrings(int minLength, int maxLength, int zeroGroup, int oneGroup) {
        const int MOD = 1000000007;
        int[] dp = new int[maxLength + 1];
        dp[0] = 1; // 空字符串是一种有效的初始状态

        for (int i = 0; i <= maxLength; i++) {
            if (i + zeroGroup <= maxLength) {
                dp[i + zeroGroup] = (dp[i + zeroGroup] + dp[i]) % MOD;
            }
            if (i + oneGroup <= maxLength) {
                dp[i + oneGroup] = (dp[i + oneGroup] + dp[i]) % MOD;
            }
        }

        int result = 0;
        for (int i = minLength; i <= maxLength; i++) {
            result = (result + dp[i]) % MOD;
        }

        return result;
    }

    public static void Main(string[] args) {
        Solution solution = new Solution();

        // 示例 1
        int minLength1 = 2, maxLength1 = 3, zeroGroup1 = 2, oneGroup1 = 1;
        int result1 = solution.CountGoodBinaryStrings(minLength1, maxLength1, zeroGroup1, oneGroup1);
        Console.WriteLine($"Example 1: {result1}"); // 输出: 5

        // 示例 2
        int minLength2 = 4, maxLength2 = 4, zeroGroup2 = 3, oneGroup2 = 4;
        int result2 = solution.CountGoodBinaryStrings(minLength2, maxLength2, zeroGroup2, oneGroup2);
        Console.WriteLine($"Example 2: {result2}"); // 输出: 1
    }
}

5. 示例解析

示例 1
输入：minLength = 2, maxLength = 3, zeroGroup = 2, oneGroup = 1
输出：5
解释：满足条件的好二进制字符串有 “00”, “11”, “001”, “100”, “111”。
示例 2
输入：minLength = 4, maxLength = 4, zeroGroup = 3, oneGroup = 4
输出：1
解释：满足条件的好二进制字符串只有 “1111”。