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

---

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();// 示例 1int minLength1 = 2, maxLength1 = 3, zeroGroup1 = 2, oneGroup1 = 1;int result1 = solution.CountGoodBinaryStrings(minLength1, maxLength1, zeroGroup1, oneGroup1);Console.WriteLine($"Example 1: {result1}"); // 输出: 5// 示例 2int 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”。

6. 总结

通过动态规划，我们可以高效地计算出满足条件的好二进制字符串的数量。动态规划的核心思想是通过状态转移方程逐步构建解，从而避免重复计算。