Description

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 ${10}^9+7$$10^9 + 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

Thinking

Yet another Dynamic Programming problem! To first identify if a problem can be solved by DP, we can see if it can be divided into smaller sub-problems. In this case, the first idea that came to my mind is knapsack problem which is a classic DP problem. The transformation: Two operation, append zero and append one is like two items with value of zero and one. In total of how many possible ways to buy item zero and item one such that the cost is between low and high. To be aware that the order here is relevant. Let's starting from the recursive approach to understand the ideology.

Top-down approach (Recursion)

x
class Solution {
    const int mod = 1e9 + 7;
public:
    int recur(int ptr, int zero, int one, vector<int>& memo) {
        if(ptr < 0) return 0;

        if(memo[ptr] != -1) return memo[ptr];

        memo[ptr] = (recur(ptr-zero, zero, one, memo) + recur(ptr-one, zero, one, memo)) % mod;

        return memo[ptr];
    }
    int countGoodStrings(int low, int high, int zero, int one) {
        vector<int> memo(high + 1, -1);
        memo[0] = 1;
        
        int ans = 0;
        for(int i=low; i<=high;++i) {
            ans += recur(i, zero, one, memo);
            ans = ans % mod;
        }

        return ans;
    }
};

For the recursive approach, the memoization is necessary, otherwise it would be very likely to TLE (Time Limit Exceed). Avoiding the repeated calculation is one of the core objectives in DP.

For a specific amount of 'money' x, the number of ways to buy items f(x) is the sum of f(x-zero) and f(x-one). The recursion's termination condition is when the parameter of f(x) becomes negative. The base case is when x=0, there is only 1way to perform.

Bottom-up approach (Iteration)

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

        for(int i=0;i<=high;++i) {
            int zero_prev = i-zero < 0 ? 0 : dp[i-zero];
            int one_prev = i-one < 0 ? 0 : dp[i-one];
            dp[i] += (zero_prev + one_prev) % mod ;
        }

        int res = 0;
        for(int i=low;i<=high;++i) {
            res = (res + dp[i]) % mod;
        }

        return res;
    }
};

It's pretty much the same. We starting from the base case dp[0] = 1, for every higher x, we get it's f(x) from the previous status.

What I learned

General steps of solving DP problems:

• Thinking about the transition. How to solve the big problem by sub-problems. Identify the base case / termination condition.

• Try to use recursion to simulate the sub-problem segmentation process.

• Adding memoization to the recursion to avoid repeated calculation. Specifically, you need to a way to identify the stage of this problem and find if this stage has already been calculated. In most cases, that stage is the index of the DP array in bottom-up approach.

• Try to transform to the bottom-up approach (Optimal solution) .