统计构造好字符串的方案数

标签: 动态规划

难度: Medium

给你整数 zero ，one ，low 和 high ，我们从空字符串开始构造一个字符串，每一步执行下面操作中的一种：

  • 将 '0' 在字符串末尾添加 zero  次。
  • 将 '1' 在字符串末尾添加 one 次。

以上操作可以执行任意次。

如果通过以上过程得到一个 长度 在 low 和 high 之间（包含上下边界）的字符串，那么这个字符串我们称为 好 字符串。

请你返回满足以上要求的 不同 好字符串数目。由于答案可能很大，请将结果对 109 + 7 取余 后返回。

示例 1：

输入：low = 3, high = 3, zero = 1, one = 1
输出：8
解释：
一个可能的好字符串是 "011" 。
可以这样构造得到："" -> "0" -> "01" -> "011" 。
从 "000" 到 "111" 之间所有的二进制字符串都是好字符串。

示例 2：

输入：low = 2, high = 3, zero = 1, one = 2
输出：5
解释：好字符串为 "00" ，"11" ，"000" ，"110" 和 "011" 。

提示：

  • 1 <= low <= high <= 105
  • 1 <= zero, one <= low

Submission

运行时间: 91 ms

内存: 20.3 MB

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

Explain

本题解使用了动态规划的方法来计算所有可能的好字符串的数目。定义dp数组，其中dp[i]表示长度为i的字符串的构造方案数。数组初始化为dp[0] = 1（空字符串有一种构造方式），其余为0。对于每个长度i（从1到high），更新dp[i]的值，通过检查是否可以从长度i-one或i-zero的字符串通过添加'1'或'0'来达到长度i。最后，将low到high之间的所有dp值求和得到答案。

时间复杂度: O(high)

空间复杂度: O(high)

class Solution:
    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:
        MOD = 10 ** 9 + 7
        dp = [1] + [0] * (high + 1)  # 初始化dp数组，dp[0]为1表示空字符串的一种构造方式
        for i in range(1, high + 1):
            if i >= one:
                dp[i] = (dp[i] + dp[i - one]) % MOD  # 如果可以加one个'1'达到长度i，增加相应的方案数
            if i >= zero:
                dp[i] = (dp[i] + dp[i - zero]) % MOD  # 如果可以加zero个'0'达到长度i，增加相应的方案数
        return sum(dp[low:]) % MOD  # 计算low到high长度的字符串的总方案数

Explore

在动态规划中初始化dp[0]为1是因为长度为0的字符串（即空字符串）只有一种构造方式，就是什么也不做。这个初始化提供了递推的基础，使得当我们在计算更长的字符串的方案数时，可以正确地从这个基础情况累加起来。

在更新dp数组时，检查长度i-one和i-zero是为了确保只有当当前长度i减去添加的字符'1'或'0'的数目（one或zero）仍然为非负时，这种构造方式才是有效的。这样的检查确保我们可以从一个有效的较短字符串通过添加相应数量的'1'或'0'来构造出长度为i的字符串。这也避免了指向dp数组无效索引的错误访问。

在这个动态规划算法中，每个dp[i]只被计算一次，并且每次计算都是基于前面的结果dp[i-one]和dp[i-zero]。通过这种方式，我们确保了在计算dp[i]时，之前计算的每个字符串长度的方案数都已被考虑，而不会被重复计算。这种从小到大计算并存储结果的方法避免了重复计算的问题。

使用求和然后取余的方法是为了防止在累加过程中结果数值过大导致的整数溢出问题，同时也是为了满足可能的计算结果要求。MOD通常是一个大质数，如10^9+7，它可以确保结果在一个可管理的范围内，并且取余操作是在确保在数学上结果仍然正确的前提下，符合给定的模数约束。