本文讲解如何将暴力递归的字符串构造问题转化为高效记忆化递推，通过仅跟踪长度而非实际字符串，将指数时间复杂度降至线性级别。
本文讲解如何将暴力递归的字符串构造问题转化为高效记忆化递推，通过仅跟踪长度而非实际字符串，将指数时间复杂度降至线性级别。
在给定约束下（每次只能追加 zero 个 '0' 或 one 个 '1'），目标是统计所有长度在 [low, high] 范围内的合法字符串总数。原始实现试图真实生成并拼接字符串（如 s + a），导致大量重复计算与内存开销，时间复杂度呈指数级增长（O(2ⁿ)），必然超时。
核心优化思想：放弃构造字符串，转而定义状态为「长度为 k 的字符串有多少种构造方式」。
设 dp[k] 表示恰好构成长度为 k 的字符串的方案数。状态转移逻辑清晰：
- 若当前长度为 k，它可能由长度 k - zero 的字符串末尾添加 zero 个 '0' 得到；
- 或由长度 k - one 的字符串末尾添加 one 个 '1' 得到。
因此递推关系为：dp[k] = dp[k - zero] + dp[k - one]
边界条件：dp[0] = 1（空字符串视为 1 种基础方案），对 k < 0 返回 0。
为避免重复递归计算，我们采用记忆化（自顶向下）或直接迭代（自底向上）实现。以下是 Java 中推荐的记忆化递归写法（配合 HashMap 或数组缓存）：
public int countGoodStrings(int low, int high, int zero, int one) {
Map<Integer, Integer> memo = new HashMap<>();
// 记忆化递归函数：返回恰好构造长度为 k 的字符串方案数
java.util.function.Function<Integer, Integer> dfs = new java.util.function.Function<>() {
@Override
public Integer apply(Integer k) {
if (k < 0) return 0;
if (k == 0) return 1;
if (memo.containsKey(k)) return memo.get(k);
int res = (apply(k - zero) + apply(k - one)) % 1_000_000_007;
memo.put(k, res);
return res;
}
};
int total = 0;
for (int len = low; len <= high; len++) {
total = (total + dfs.apply(len)) % 1_000_000_007;
}
return total;
}✅ 关键注意事项：
- 不要传入字符串参数或拼接操作——这是性能杀手；只传递整数长度 k；
- 模运算 % 1_000_000_007 应在每次加法后及时应用，防止整数溢出；
- 可进一步优化为空间 O(high) 的迭代 DP（一维数组），但记忆化递归更直观、易验证逻辑；
- 示例输入 low=2, high=3, zero=1, one=2：
dp[0]=1, dp[1]=dp[0]=1, dp[2]=dp[1]+dp[0]=2, dp[3]=dp[2]+dp[1]=3 → 总和 dp[2]+dp[3] = 2+3 = 5，结果正确。
该方法将时间复杂度优化至 O(high)，空间复杂度 O(high)，彻底规避 TLE，是典型「状态抽象 + 记忆化」优化范式。
