2466. Count Ways To Build Good Strings

解題心得

推導後會發現這是爬樓梯問題的變化版。

程式碼

class Solution {
public:
    int countGoodStrings(int low, int high, int zero, int one) {
        vector<int> dp(high + 1, 0);
        dp[0] = 1;

        int count = 0, mod = 1e9 + 7;
        for(int i=1; i<=high; i++)
        {
            dp[i] = (i >= zero ? dp[i-zero] : 0) + (i >= one ? dp[i-one] : 0);
            dp[i] %= mod;
            if(low <= i && i <= high)
                count = (count + dp[i]) % mod;
        }
        return count;
    }
};