2466. 统计构造好字符串的方法数 - Count Ways To Build Good Strings

🎯 问题描述（来源于LeetCode）

描述：
给你整数 low、high、zero 和 one。请你构造字符串，每次操作可以添加 zero 个 '0' 或添加 one 个 '1'。
求最终字符串的长度在 [low, high] 之间的不同构造方法数。答案对 10^9+7 取模。

说明：

  • 空字符串是允许的初始状态。
  • 每次操作必须添加恰好 zero 个 '0' 或恰好 one 个 '1'，不能部分添加。

示例：

  • 示例 1：
1
2
3
输入: low = 3, high = 3, zero = 1, one = 1
输出: 8
解释: 长度为3的字符串有8种（每位可以是0或1）。
  • 示例 2：
1
2
3
输入: low = 2, high = 3, zero = 1, one = 2
输出: 5
解释: 长度为2：00,11；长度为3：000,011,110；共5种。

💻 解题思路

思路：动态规划（爬楼梯变种）

算法步骤

  1. 定义 dp[i] 表示构造长度为 i 的字符串的不同方法数。
  2. 初始化 dp[0] = 1（空字符串有一种方法）。
  3. 对于 i 从 1 到 high：
    • 如果 i >= zero，则 dp[i] += dp[i - zero]。
    • 如果 i >= one，则 dp[i] += dp[i - one]。
    • 每次加和后取模 mod = 1_000_000_007。
  4. 最终答案 = (dp[low] + dp[low+1] + ... + dp[high]) % mod。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
from typing import List

class Solution:
    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:
        dp = [1] + [0] * high
        mod = 1_000_000_007
        for i in range(1, high + 1):
            if i >= zero:
                dp[i] = dp[i - zero]
            if i >= one:
                dp[i] = (dp[i] + dp[i - one]) % mod
        return sum(dp[low:]) % mod

📊 性能分析

  • 时间复杂度：O(high)O(high)，只需一次遍历。
  • 空间复杂度：O(high)O(high)，存储 dp 数组。

思考

本题与爬楼梯问题类似，区别在于步长 zero 和 one 是固定的，且要求统计长度在某个区间内的所有方案数。用户代码使用了优化的写法：先计算当前 dp[i] 等于 dp[i-zero]（如果可达），再累加 dp[i-one]（如果可达），避免了重复的 + 操作。最后通过切片求和得到区间内所有长度的方案总数，取模返回。该解法清晰高效，是本题的标准答案。