爬楼梯变式

2466. 统计构造好字符串的方案数 - 力扣（LeetCode）

解析见注释：

class Solution 
{
public:int countGoodStrings(int low, int high, int zero, int one) {//每次能爬zero或one个台阶，问爬的台阶数在low到high之间的方案数const int MOD=1'000'000'007;int ans=0;vector<int>dp(high+1);//dp[i]表示构造长为i的字符串的方案数dp[0]=1;//构造空串有1种方法for(int i=1;i<=high;i++){//有两种方法可以得到长度为i的字符串//1.在长度为i-zero的串后添加zero个0//2.在长度为i-one的串后添加one个1//由于最后一个字符不可能既是0又是1，因此dp[i]等于两者之和//对于1，要有：i>=zero，对于2要有：i>=one，但这并不是“且”的关系//所以不能直接写dp[i]=dp[i-zero]+dp[i-one]，要拆成两步if(i>=zero) dp[i]=dp[i-zero];//无需取模，因为方案数并没有增加if(i>=one) dp[i]=(dp[i]+dp[i-one])%MOD;//提前取模，否则可能已经算出爆内存的数字但还在往后算if(i>=low) ans=(ans+dp[i])%MOD;}return ans;}
};