如何用记忆化递归高效计算满足长度约束的二进制字符串数量-java教程-PHP中文网

如何用记忆化递归高效计算满足长度约束的二进制字符串数量

本文讲解如何将暴力生成字符串的指数级解法优化为时间复杂度 O(high) 的记忆化递归方案，核心是放弃构造字符串，转而定义 dp[k] 为恰好长度为 k 的合法字符串数量，并利用子问题重叠进行缓存。

本文讲解如何将暴力生成字符串的指数级解法优化为时间复杂度 o(high) 的记忆化递归方案，核心是放弃构造字符串，转而定义 `dp[k]` 为恰好长度为 k 的合法字符串数量，并利用子问题重叠进行缓存。

该问题本质是一个计数型动态规划问题：从空串出发，每次只能追加 zero 个 '0' 或 one 个 '1'（即长度分别增加 zero 或 one），求最终长度落在 [low, high] 区间内的所有不同字符串总数。

原始代码的问题在于：

实际拼接字符串（如 s + a），时间和空间开销巨大；
未去重且反复计算相同长度的子问题（例如多次计算“长度为 2 的方案数”）；
递归无记忆，导致时间复杂度呈指数级增长（TLE）。

✅ 正确思路是：只关心字符串长度，不关心具体内容。
定义状态：
dp[k] = 恰好构成长度为 k 的合法字符串的方案总数。

状态转移方程：

若当前长度为 k，它可能由长度 k - zero 的串末尾加 zero 个 '0' 得到；
也可能由长度 k - one 的串末尾加 one 个 '1' 得到。
因此：
```
dp[k] = dp[k - zero] + dp[k - one]
```
边界条件：dp[0] = 1（空串是一种方案），对 k

ViiTor AI
ViiTor AI是一款面向视频翻译、配音、口型同步和多语言内容本地化的 AI 视频工具。

下载

使用记忆化（如哈希表或数组缓存）避免重复计算。推荐用数组 dp[0..high]，初始化 dp[0] = 1，其余为 0，正向递推更清晰：

public int countGoodStrings(int low, int high, int zero, int one) {
    int[] dp = new int[high + 1];
    dp[0] = 1; // 空串为唯一基础方案

    for (int len = 1; 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 <p>⚠️ 注意事项：</p>