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

一、题目解读

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] 表示长度为 i 的好字符串方案数。

2. 转移方程：

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

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

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

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

三、解题步骤

1. 初始化：

○ 定义模数 MOD = 1e9 + 7，避免整数溢出。

○ 创建 dp 数组并初始化，dp[0] = 1（空字符串合法）。

2. 动态规划循环，遍历长度 i=1 到 high，对每个长度：

    若 i >= zero，将 dp[i-zero] 累加至 dp[i]（可扩展 zero 个 '0'）。

    若 i >= one，将 dp[i-one] 累加至 dp[i]（可扩展 one 个 '1'）。

    每次累加后取模，确保结果合法。

3. 统计答案：

○ 遍历 i=low 到 high，累加 dp[i] 至结果变量 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. 累加目标区间内的合法方案数。

该算法简洁高效，适用于组合计数类问题的求解，是动态规划的经典应用案例。