Leetcode6238-统计构造好字符串的方案数

dp

        定义状态f[i]为能构造长度为i的字符串的种类，则状态转移方程为：

gif.latex?f" role="presentation">gif.latex?f$gif.latex?f$

        依次递推到长度大于等于high为止，答案为low到high之间的总和。

class Solution {
public:
    const int mod=1e9+7;
    long long ans=0;
    int countGoodStrings(int low, int high, int zero, int one) {
        int dp[high+1];
        memset(dp,0,sizeof dp);
        dp[0]=1;
        for(int i=0;i<=high;i++){
            if(i>=zero) dp[i]=dp[i-zero];
            if(i>=one) dp[i]=(1LL*dp[i]+dp[i-one])%mod;
            if(i>=low) ans=(ans+1LL*dp[i])%mod;
        }
        return ans;
    }
};

时间复杂度：O（n）

空间复杂度：O（n）