【LeetCode】动态规划—2466. 统计构造好字符串的方案数（附完整Python/C++代码）

题目描述

前言

在本问题中，我们需要计算构建良好字符串的方式。给定两个整数 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)) % MOD
        return 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 数组。