2466. 统计构造好字符串的方案数

🟠 🔖 动态规划 🔗 力扣open in new window LeetCodeopen in new window

题目

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

题目大意

给你整数 zero ，one ，low 和 high ，我们从空字符串开始构造一个字符串，每一步执行下面操作中的一种：

将 '0' 在字符串末尾添加 zero 次。
将 '1' 在字符串末尾添加 one 次。

以上操作可以执行任意次。

如果通过以上过程得到一个长度在 low 和 high 之间（包含上下边界）的字符串，那么这个字符串我们称为好字符串。

请你返回满足以上要求的不同好字符串数目。由于答案可能很大，请将结果对 109 + 7 取余后返回。

示例 1：

输入： low = 3, high = 3, zero = 1, one = 1
输出： 8
解释：
一个可能的好字符串是 "011" 。
可以这样构造得到："" -> "0" -> "01" -> "011" 。
从 "000" 到 "111" 之间所有的二进制字符串都是好字符串。

示例 2：

输入： low = 2, high = 3, zero = 1, one = 2
输出： 5
解释： 好字符串为 "00" ，"11" ，"000" ，"110" 和 "011" 。

提示：

1 <= low <= high <= 10^5
1 <= zero, one <= low

解题思路

状态定义

定义 dp[i] 表示长度为 i 的好字符串的数量。

状态转移

长度为 i 的字符串可以通过以下两种方式生成：

在长度为 i - zero 的字符串后面添加长度为 zero 的 '0'。
在长度为 i - one 的字符串后面添加长度为 one 的 '1'。

因此，状态转移方程为：dp[i] = dp[i - zero] + dp[i - one] 注意要对结果取模 10^9 + 7。

初始状态

长度为 0 的好字符串只有一种（空字符串），因此 dp[0] = 1。

结果计算

遍历范围 [low, high]，将所有长度在该范围内的 dp[i] 累加，得到答案。

复杂度分析

时间复杂度：O(high)
- 填充 dp 数组需要遍历 1 到 high，时间复杂度为O(high)。
- 遍历 [low, high] 累加结果，时间复杂度为 O(high - low)。
空间复杂度：O(high)，使用了长度为 high + 1 的数组 dp。

代码

/**
 * @param {number} low
 * @param {number} high
 * @param {number} zero
 * @param {number} one
 * @return {number}
 */
var countGoodStrings = function (low, high, zero, one) {
	const mod = 10 ** 9 + 7;
	let dp = new Array(high + 1).fill(0);
	dp[0] = 1; // 长度为 0 的情况
	let res = 0;

	for (let i = 1; i <= high; i++) {
		if (i >= zero) dp[i] = dp[i - zero]; // 加入零
		if (i >= one) dp[i] = (dp[i] + dp[i - one]) % mod; // 加入一
		if (i >= low) res = (res + dp[i]) % mod; // 在 [low, high] 范围内累加结果
	}

	return res;
};

2466. 统计构造好字符串的方案数

# 2466. 统计构造好字符串的方案数

# 题目

# 题目大意

# 解题思路

# 复杂度分析

# 代码

# 相关题目

2466. 统计构造好字符串的方案数

题目

题目大意

解题思路

复杂度分析

代码

相关题目