LeetCode 2466题解：统计构造好字符串的方案数（动态规划+模...

15303105423 · 发表于 2025-7-19 10:32:23

一、题目解读

LeetCode 2466题要求统计在长度范围 [low, high] 内，由字符 '0' 和 '1' 构成的“好字符串”数量。好字符串定义为：每次可添加 zero 个 '0' 或 one 个 '1' 扩展，且最终长度在合法区间内。例如，当 low=2, high=3, zero=1, one=2 时，合法字符串包括 "011"、"110"、"000" 等，方案数为 5。题目难点在于高效计算符合约束条件的组合数。

二、解题思路

采用“动态规划+模运算”策略，核心思想是将问题拆解为子问题的组合：

1. 状态定义：使用动态规划数组 dp 表示长度为 i 的好字符串方案数。

2. 转移方程：

○ 若 i >= zero，可在前 i-zero 长度字符串末尾添加 zero 个 '0'，即 dp += dp[i-zero]；

○ 若 i >= one，可在末尾添加 one 个 '1'，即 dp += dp[i-one]。

3. 边界条件：空字符串（长度0）为一种合法方案，即 dp[0] = 1。

4. 累加结果：遍历 [low, high] 区间内的 dp 值求和，并通过取模防止溢出。

三、解题步骤
1. 初始化：
○ 定义模数 MOD = 1e9 + 7，避免整数溢出。
○ 创建 dp 数组并初始化，dp[0] = 1（空字符串合法）。
2. 动态规划循环，遍历长度 i=1 到 high，对每个长度：
若 i >= zero，将 dp[i-zero] 累加至 dp（可扩展 zero 个 '0'）。
若 i >= one，将 dp[i-one] 累加至 dp（可扩展 one 个 '1'）。
每次累加后取模，确保结果合法。
3. 统计答案：
○ 遍历 i=low 到 high，累加 dp 至结果变量 result，并取模。
4. 返回结果：最终 result 即为方案总数。
四、代码及注释

class Solution {

public:

int countGoodStrings(int low, int high, int zero, int one) {

      const int MOD = 1e9 + 7;       // 定义模数防止溢出

      vector<int> dp(high + 1, 0);    // 动态规划数组，初始化为0

      dp[0] = 1;                      // 空字符串为一种方案



      // 动态规划：计算每个长度的合法方案数

      for (int i = 1; i <= high; ++i) {

         // 如果可以在末尾添加zero个'0'

         if (i >= zero) {

            dp[i] = (dp[i] + dp[i - zero]) % MOD;  // 累加方案并取模

         }

         // 如果可以在末尾添加one个'1'

         if (i >= one) {

            dp[i] = (dp[i] + dp[i - one]) % MOD;  // 累加方案并取模

         }

      }



      // 累加[low, high]范围内的方案数

      int result = 0;

      for (int i = low; i <= high; ++i) {

         result = (result + dp[i]) % MOD;    // 累加并取模

      }



      return result;                            // 返回最终结果

}

};
复制代码

五、总结
本解法通过动态规划将大问题分解为子问题，利用模运算优化避免溢出，时间复杂度为 O(high)，空间复杂度为 O(high)。关键点包括：
1. 明确状态转移方程，通过已有方案推导新方案；
2. 边界条件处理（空字符串作为起始状态）；
3. 累加目标区间内的合法方案数。
该算法简洁高效，适用于组合计数类问题的求解，是动态规划的经典应用案例。
来源：力扣题解

LeetCode 2466题解：统计构造好字符串的方案数（动态规划+模...

浏览过的版块