2466. Count Ways To Build Good Strings

  • Hardness: \(\color{orange}\textsf{Medium}\)
  • Ralated Topics: Dynamic Programming
  • \(\color{blue}\textsf{Biweekly Contest 91}\)

一、題目

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.

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 <= 10^5
  • 1 <= zero, one <= low

二、分析

  • 這一題與 322. Coin Change 有異曲同工之妙。
  • 這一題動態規劃是不定序列型框架的題型：
    • dp[n] 設為組成長度為 n 的 string 的可能性，最後再將符合題目需求的 dp[low] 到 dp[high] 加起來。
    • dp[n] = sum(dp[n-nums[i]])。

三、解題

1. DP

  • Time complexity: \(O(n)\)
  • Space complexity: \(O(n)\)
int countGoodStrings(int low, int high, int zero, int one) {
    vector<int> dp(high+1, 0);
    int res = 0;
    dp[0] = 1;
    int start = min(zero, one);
    for (int i = start; i <= high; i++) {
        if (i-zero >= 0) dp[i] = (dp[i] + dp[i-zero]) % modulo;
        if (i-one >= 0) dp[i] = (dp[i] + dp[i-one]) % modulo;
        if (i >= low) res = (res + dp[i]) % modulo;
    }
    return res;
}

回目錄 Catalog