标签: 动态规划
难度: Medium
Submission
运行时间: 154 ms
内存: 20.2 MB
MOD = 10 ** 9 + 7
class Solution:
def goodBinaryStrings(self, minLength: int, maxLength: int, oneGroup: int, zeroGroup: int) -> int:
dp = [0] * (maxLength + 1)
dp[0] = 1
for i in range(1, maxLength + 1):
if i >= oneGroup:
dp[i] = dp[i - oneGroup]
if i >= zeroGroup:
dp[i] = (dp[i] + dp[i - zeroGroup]) % MOD
return sum(dp[minLength:]) % MOD
Explain
此题解采用动态规划的方法来解决“好二进制字符串的数量”问题。定义 dp[i] 表示长度为 i 的二进制字符串中满足条件的字符串数量。初始条件下，dp[0] = 1 表示长度为0的字符串（空字符串）是有效的。对于每个长度 i （从1到maxLength），若长度 i 大于等于 oneGroup，则可以在长度为 i-oneGroup 的所有好二进制字符串后附加 oneGroup 个 '1'，形成新的好二进制字符串。类似地，若长度 i 大于等于 zeroGroup，则可以在长度为 i-zeroGroup 的所有好二进制字符串后附加 zeroGroup 个 '0'。最终结果为从 minLength 到 maxLength 的所有 dp 值的和，由于可能出现大数，结果需要对 MOD 取模。
时间复杂度: O(maxLength)
空间复杂度: O(maxLength)
MOD = 10 ** 9 + 7
class Solution:
def goodBinaryStrings(self, minLength: int, maxLength: int, oneGroup: int, zeroGroup: int) -> int:
dp = [0] * (maxLength + 1) # 初始化dp数组，长度为 maxLength + 1
dp[0] = 1 # 空字符串是一个有效的字符串
for i in range(1, maxLength + 1): # 遍历每一个长度从1到maxLength
if i >= oneGroup: # 如果当前长度大于等于oneGroup
dp[i] = dp[i - oneGroup] # 在长度为i-oneGroup的字符串后加oneGroup个'1'
if i >= zeroGroup: # 如果当前长度大于等于zeroGroup
dp[i] = (dp[i] + dp[i - zeroGroup]) % MOD # 在长度为i-zeroGroup的字符串后加zeroGroup个'0'
return sum(dp[minLength:]) % MOD # 计算从minLength到maxLength的所有dp值的和，结果取模
Explore
dp[i] 仅依赖于 i-oneGroup 和 i-zeroGroup 的值，因为题目要求计算的是由特定数量的连续 '1' 或连续 '0' 组成的二进制字符串的数量。这意味着，要形成一个长度为 i 的好二进制字符串，你只需要考虑在一个已经满足条件的较短字符串后附加指定数量的 '1' 或 '0'。因此，每个 dp[i] 只需基于长度为 i-oneGroup 和 i-zeroGroup 的好二进制字符串计算，无需考虑更复杂的组合或依赖关系。
当 oneGroup 和 zeroGroup 值非常接近时，可能导致 dp[i-oneGroup] 和 dp[i-zeroGroup] 重复计算或近似相同的值。在题解中，通过累加 dp[i] = dp[i - oneGroup] 和 dp[i] = (dp[i] + dp[i - zeroGroup]) % MOD 来处理这种情况，确保每次更新都是有效的，并且通过模运算保持计算结果的稳定性。这样的处理方式虽然简单，但能够有效避免因重复或接近的值导致的计算过多。
题解中未明确‘好二进制字符串’的定义可能导致理解上的歧义，但根据题解的上下文，我们可以推断出‘好二进制字符串’指的是由连续的 '1' 组成的组和连续的 '0' 组成的组交替出现的字符串。这种特定的结构直接影响了 dp 数组的更新规则，即每次更新 dp[i] 时，只需考虑在有效的较短字符串后添加一组连续的 '1' 或 '0'。这反映了动态规划中的状态转移，仅通过添加连续的字符组来扩展已知的好字符串。
在处理涉及大数的计算问题时，常常需要对结果进行模运算以防止整数溢出和降低计算结果的存储需求。MOD = 10 ** 9 + 7 是一个常用的大质数，用于模运算可以有效避免计算溢出，并且由于其是质数，也有助于在数学运算中保持良好的分布特性。在此题中，使用 MOD 进行模运算确保所有计算步骤中的数值都能够被有效管理且保持在一个安全的范围内，同时也保证最终结果的正确性。