本文介绍如何将暴力递归生成字符串的指数级解法，转化为基于长度状态的记忆化动态规划，通过缓存子问题结果将时间复杂度降至 o(high)，高效求解满足长度约束的字符串总数。
本文介绍如何将暴力递归生成字符串的指数级解法，转化为基于长度状态的记忆化动态规划，通过缓存子问题结果将时间复杂度降至 o(high)，高效求解满足长度约束的字符串总数。
该问题本质是计数型动态规划（Counting DP），核心洞察在于：我们并不关心字符串的具体内容（如 "00" 或 "110"），只关心其长度是否在 [low, high] 范围内，且该长度能否由若干次 +zero 或 +one 操作拼凑而成。
❌ 原始方法的问题
原始代码试图实际构造所有字符串（s + a, s + b），导致：
- 时间爆炸：每层递归分支为 2，深度最多达 high，时间复杂度为 O(2high)；
- 空间浪费：频繁字符串拼接（s + a）产生大量临时对象；
- 无法复用：相同长度 len(s) 多次重复计算，无状态缓存。
✅ 正确思路：以「长度」为状态进行记忆化
定义 dp[k] = 恰好构成长度为 k 的字符串的方案数。
状态转移方程为：
dp[k] = dp[k - zero] + dp[k - one] （当 k ≥ zero 或 k ≥ one 时）
边界条件：dp[0] = 1（空字符串为唯一长度为 0 的方案）。
⚠️ 注意：k - zero 或 k - one 可能为负数，此时对应方案数为 0。
? Java 实现（带记忆化数组）
public int countGoodStrings(int low, int high, int zero, int one) {
int[] dp = new int[high + 1];
dp[0] = 1; // base case: empty string
for (int len = 1; len <= high; len++) {
if (len >= zero) dp[len] = (dp[len] + dp[len - zero]) % 1_000_000_007;
if (len >= one) dp[len] = (dp[len] + dp[len - one]) % 1_000_000_007;
}
int ans = 0;
for (int len = low; len <= high; len++) {
ans = (ans + dp[len]) % 1_000_000_007;
}
return ans;
}✅ 优势说明：
- 时间复杂度：O(high)，仅需单次遍历；
- 空间复杂度：O(high)，一维数组即可；
- 无需字符串操作，杜绝内存与性能瓶颈；
- 自然支持取模（题目常要求对 10⁹+7 取余）。
? 关键注意事项
- 不要初始化 dp 全为 -1 后再递归：本题更适合「自底向上」填表（更简洁、无栈溢出风险）；若坚持递归+记忆化，需确保 dp[0]=1 且负索引返回 0；
- zero 和 one 可能相等，但不影响状态转移（加两次也无妨，因方案独立）；
- 示例验证：low=2, high=3, zero=1, one=2
dp[0]=1
dp[1] = dp[0] = 1（仅 "0"）
dp[2] = dp[1] + dp[0] = 1 + 1 = 2（"00", "11"）
dp[3] = dp[2] + dp[1] = 2 + 1 = 3（"000", "110", "011"）
总和 = dp[2] + dp[3] = 2 + 3 = 5 ✅
掌握这种「去实体化、抓状态本质」的思维，是攻克各类组合计数 DP 题的关键。
