题目描述

前言

在本问题中，我们需要计算构建良好字符串的方式。给定两个整数 low 和 high，表示字符串的最小和最大长度，以及两个字符 zero 和 one，我们的任务是找到用这两个字符构建字符串的所有可能方式，确保构建的字符串长度在 low 到 high 之间。

---

基本思路

1. 问题定义

我们需要找出所有由字符 0 和 1 组成的字符串，其长度在 low 到 high 之间，并且字符串的构建方式是根据提供的字符构建。

举例：

• 输入：low = 3, high = 3, zero = "0", one = "1"
• 输出：1
• 解释：只有一种可能的字符串："111"，长度在范围内。

2. 理解问题和递推关系

动态规划思想：

我们可以使用动态规划来计算构建字符串的方式。定义一个数组 dp[i]，表示构建长度为 i 的字符串的方式。

状态定义：

• dp[i] 表示构建长度为 i 的字符串的方式数量。

状态转移方程：

• 对于每个长度 i，我们可以从长度 i-1 的字符串添加字符 1，或者从长度 i-2 的字符串添加字符 0：
  $$dp[i]=dp[i-1]+dp[i-2]$$
  • 其中 dp[i - 1] 是从长度 i-1 加上字符 1 的构建方式，dp[i - 2] 是从长度 i-2 加上字符 0 的构建方式。

边界条件：

• dp[0] = 1：表示构建长度为 0 的字符串有 1 种方式（即空字符串）。
• dp[1] = 1：表示构建长度为 1 的字符串只有 1 种方式（即字符 1）。

3. 解决方法

动态规划方法

1. 初始化：创建一个大小为 high + 1 的 dp 数组，初始时 dp[0] = 1，dp[1] = 1。
2. 状态转移：遍历从 2 到 high，更新 dp[i] 的值。
3. 结果计算：将 dp 数组中 low 到 high 的所有值相加，得到构建的总方式。

伪代码：

initialize dp array with dp[0] = 1, dp[1] = 1
for i from 2 to high:dp[i] = dp[i - 1] + dp[i - 2]
total_ways = sum(dp[i] for i in range(low, high + 1))
return total_ways

4. 进一步优化

• 时间复杂度：时间复杂度为 O(high)，因为我们只需遍历到 high 。
• 空间复杂度：空间复杂度为 O(high)，因为需要一个 dp 数组。

5. 小总结

• 递推思路：通过动态规划逐步构建 dp 数组，从最小长度开始递推，计算出构建的所有方式。
• 时间复杂度：时间复杂度为 O(high)，适合处理中等规模的输入。

以上就是统计构造好字符串的方案数问题的基本思路。

---

Python代码

class Solution:def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:MOD = 10**9 + 7# dp[i] 表示长度为 i 的良好字符串的数量dp = [0] * (high + 1)dp[0] = 1  # 空字符串的方式for i in range(1, high + 1):if i >= one:dp[i] = (dp[i] + dp[i - one]) % MOD  # 添加字符 '1'if i >= zero:dp[i] = (dp[i] + dp[i - zero]) % MOD  # 添加字符 '0'# 计算从 low 到 high 的总和total_ways = sum(dp[i] for i in range(low, high + 1)) % MODreturn total_ways

Python代码解释

1. 初始化：定义 dp 数组，dp[i] 表示构建长度为 i 的字符串的方式，初始时 dp[0] = 1。
2. 动态规划递推：遍历长度 1 到 high，更新 dp[i]，即计算出当前长度 i 的字符串的构建方式。
3. 结果计算：求和 low 到 high 的所有方式，返回结果。

---

C++代码

class Solution {
public:int countGoodStrings(int low, int high, int zero, int one) {const int MOD = 1e9 + 7;// dp[i] 表示长度为 i 的良好字符串的数量vector<long long> dp(high + 1, 0);dp[0] = 1;  // 空字符串的方式for (int i = 1; i <= high; ++i) {if (i >= one) {dp[i] = (dp[i] + dp[i - one]) % MOD;  // 添加字符 '1'}if (i >= zero) {dp[i] = (dp[i] + dp[i - zero]) % MOD;  // 添加字符 '0'}}// 计算从 low 到 high 的总和long long total_ways = 0;for (int i = low; i <= high; ++i) {total_ways = (total_ways + dp[i]) % MOD;}return total_ways;}
};

C++代码解释

1. 初始化：定义 dp 数组，dp[i] 表示构建长度为 i 的字符串的方式，初始时 dp[0] = 1。
2. 动态规划递推：遍历长度 1 到 high，更新 dp[i]，即计算出当前长度 i 的字符串的构建方式。
3. 结果计算：求和 low 到 high 的所有方式，返回结果。

---

总结

• 核心思想：通过动态规划计算构建字符串的方式，使用状态转移方程 dp[i] = dp[i-1] + dp[i-2] 来更新每个长度的构建方式。
• 时间复杂度：时间复杂度为 O(high)，因为只需遍历到 high 。
• 空间复杂度：空间复杂度为 O(high)，因为需要一个 dp 数组。