力扣2466详解：动态规划巧解字符串构造问题

一、问题理解

我们需要计算通过特定操作构造的字符串数量，这些字符串的长度必须在给定范围内。每次操作可以选择添加固定数量的'0'或'1'。

二、解题思路

1. ‌动态规划定义‌：DP[i]表示长度为i的字符串的构造方式数

2. ‌状态转移‌：

• dp[i] += dp[i-zero] (如果可以添加zero个'0')

• dp[i] += dp[i-one] (如果可以添加one个'1')

3. ‌结果计算‌：累加dp[low]到dp[high]的值

三、代码详解

class Solution {
public:
    int countGoodStrings(int low, int high, int zero, int one) {
        const int MOD = 1e9 + 7;
        vector<int> dp(high + 1, 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)，需要遍历1到high的所有长度

• 空间复杂度：O(high)，需要存储DP数组

五、优化思考

1. 可以优化空间复杂度到O(max(zero,one))

2. 预处理zero和one的最小公倍数可能有优化空间