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

友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

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

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

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

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

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

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

请你返回满足以上要求的不同好字符串数目。由于答案可能很大，请将结果对 10⁹ + 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⁵
1 <= zero, one <= low

思路分析

还是爬楼梯！脑子转不过来弯！

爬楼梯解法：\(f(i) = f(i−zero) + f(i − one)\)。

一刷
二刷(暴力破解)
二刷(备忘录)
二刷(动态规划)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2025-09-29 23:03:47
 */
public int countGoodStrings(int low, int high, int zero, int one) {
  int[] memo = new int[high + 1];
  Arrays.fill(memo, -1);
  int result = 0;
  for (int i = low; i <= high; i++) {
    result = (result + dfs(i, zero, one, memo)) % 1_000_000_007;
  }
  return result;
}

private int dfs(int i, int zero, int one, int[] memo) {
  if (i < 0) {
    return 0;
  }
  if (i == 0) {
    return 1;
  }
  if (memo[i] != -1) {
    return memo[i];
  }
  memo[i] = (dfs(i - zero, zero, one, memo)
    + dfs(i - one, zero, one, memo)) % 1_000_000_007;
  return memo[i];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * 暴力破解（14/36）->
 *
 * @author D瓜哥 · https://www.diguage.com
 * @since 2026-01-03 10:05:29
 */
public int countGoodStrings(int low, int high, int zero, int one) {
  int mod = 1_000_000_007;
  int result = 0;
  for (int i = low; i <= high; i++) {
    result += dfs(i, zero, one, mod);
    result %= mod;
  }
  return result;
}

private int dfs(int length, int zero, int one, int mod) {
  if (length == 0) {
    return 1;
  }
  int a = length >= zero ? dfs(length - zero, zero, one, mod) : 0;
  int b = length >= one ? dfs(length - one, zero, one, mod) : 0;
  return (a + b) % mod;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * 暴力破解（14/36）-> 备忘录（12.65%）
 *
 * @author D瓜哥 · https://www.diguage.com
 * @since 2026-01-03 10:20:23
 */
public int countGoodStrings(int low, int high, int zero, int one) {
  int mod = 1_000_000_007;
  int[] memo = new int[high + 1];
  Arrays.fill(memo, -1);
  int result = 0;
  for (int i = low; i <= high; i++) {
    result += dfs(i, zero, one, mod, memo);
    result %= mod;
  }
  return result;
}

private int dfs(int length, int zero, int one, int mod, int[] memo) {
  if (length == 0) {
    return 1;
  }
  if (memo[length] >= 0) {
    return memo[length];
  }
  // f(i) = f(i-zero) + f(i-one)
  int a = length >= zero ? dfs(length - zero, zero, one, mod, memo) : 0;
  int b = length >= one ? dfs(length - one, zero, one, mod, memo) : 0;
  return memo[length] = (a + b) % mod;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * 暴力破解（14/36）-> 备忘录（12.65%）-> 动态规划（33.45%）
 *
 * @author D瓜哥 · https://www.diguage.com
 * @since 2026-01-03 10:27:06
 */
public int countGoodStrings(int low, int high, int zero, int one) {
  int mod = 1_000_000_007;
  // f(i) = f(i-zero) + f(i-one)
  int[] dp = new int[high + 1];
  dp[0] = 1;
  int[] steps = {zero, one};
  Arrays.sort(steps);
  for (int i = 0; i <= high - steps[0]; i++) {
    for (int step : steps) {
      if (i + step > high) {
        break;
      }
      dp[i + step] += dp[i];
      dp[i + step] %= mod;
    }
  }
  int result = 0;
  for (int i = low; i <= high; i++) {
    result += dp[i];
    result %= mod;
  }
  return result;
}

还可以利用最大公约数来优化时间复杂度。回头可以看看。

参考资料

2466. 统计构造好字符串的方案数 - 爬楼梯换皮 — 最后的优化真是太绝了！
2466. 统计构造好字符串的方案数