题解 | 统计构造好字符串的方法数

题干分析

题设给予我们四个正整数（以下取首字母z,o,l,h），从一个空字符串我们可以进行若干次以下操作：

• 在字符串末尾接上z个字符'0'
• 在字符串末尾接上o个字符'1' 要求最后得到的字符串长度在区间内，求符合要求的字串数（模）

算法思路

拆分问题：

我们得到的最终字符串只可能从两种情况下得来：

• 通过一个字符串末尾添加z个字符'0'
• 通过一个字符串末尾添加o个字符'1'

设数组值dp[i]表示依据题设构造一个长为i的字符串的方法数，不难得到DP状态转移方程如下：

同时我们设定DP初始条件为

计算完成后将i从l循环递增到h求dp[i]的值之和输出即可。

注意全程在计算时需要追加模计算。

实现代码

class Solution {
    const int M = 1000000007;

    int addMod(int a, int b) {
        long long tmp = static_cast<long long>(a) + b;
        return static_cast<int>(tmp % M);
    }
public:
    int countGoodStrings(int low, int high, int zero, int one) {
        vector<int> dp(high + 1);
        dp[0] = 1;
        for (int i = 1; i <= high; ++i) {
            if (i >= zero) dp[i] = addMod(dp[i], dp[i - zero]);
            if (i >= one) dp[i] = addMod(dp[i], dp[i - one]);
        }
        int ans = 0;
        for (int i = low; i <= high; ++i) ans = addMod(ans, dp[i]);
        return ans;
    }
};

复杂度分析

• 时间复杂度：从0-h每个状态计算一次，总计时间复杂度为
• 空间复杂度：dp数组空间开销为主，总计