Count Ways To Build Good Strings(Dynamic Programming)

https://leetcode.com/problems/count-ways-to-build-good-strings/description/?envType=daily-question&envId=2024-12-30

Given the integers zero, one, low, and high, we can construct a string by starting with an empty string, and then at each step perform either of the following:

• Append the character '0' zero times.
• Append the character '1' one times.

This can be performed any number of times.

A good string is a string constructed by the above process having a length between low and high (inclusive).

Return the number of different good strings that can be constructed satisfying these properties. Since the answer can be large, return it modulo 109 + 7.

 

Example 1:

Input: low = 3, high = 3, zero = 1, one = 1
Output: 8
Explanation: 
One possible valid good string is "011". 
It can be constructed as follows: "" -> "0" -> "01" -> "011". 
All binary strings from "000" to "111" are good strings in this example.

Example 2:

Input: low = 2, high = 3, zero = 1, one = 2
Output: 5
Explanation: The good strings are "00", "11", "000", "110", and "011".

 

Constraints:

• 1 <= low <= high <= 105
• 1 <= zero, one <= low

또 DP 문제다.

 

DP의 기본은 Memoization을 사용하는 것! 과연 이번엔 쉽사리 문제를 해결할 수 있을런지..

 

어렵다 모르겄다~

 

GG치고 답지봤다.

 

1. Python

class Solution:
    def countGoodStrings(self, low: int, high: int, zero: int, one: int) -> int:
        mod = 10**9 + 7

        dp = [0] * (high + 1)
        dp[0] = 1 # Base case : one way to make an empty sting

        for i in range(1,high+1):
            if i >= zero :
                dp[i] = (dp[i] + dp[i-zero]) % mod
            if i >= one :
                dp[i] = (dp[i] + dp[i-one]) % mod
        result = 0
        for i in range(low,high+1):
            result = (result + dp[i]) % mod
            
        return result

 

2. C++

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

        for(int i=1;i<=high;i++){
            if(i>=zero){
                dp[i] = (dp[i]+dp[i-zero]) % mod;
            }
            if(i>=one){
                dp[i] = (dp[i]+dp[i-one]) % mod;
            }
        }
        int ans = 0;

        for(int j=low;j<=high;j++){
            ans = (ans+dp[j]) % mod;
        }
        return ans;
    }
};