如何用记忆化（memoization）优化字符串计数问题的递归超时解法？

问题描述 #

从空字符串出发，只能做两种操作：

• 追加zero个字符'0'
• 追加one个字符'1'

给定字符串长度的范围[low, high]，统计能生成的符合长度要求的字符串总数。

示例 #

输入：low = 2, high = 3, zero = 1, one = 2
输出：5
对应的有效字符串："00"、"11"、"000"、"110"、"011"

原始递归代码（超时问题） #

你写的递归代码因为每次都要分支处理两种操作，时间复杂度是指数级的，所以会超时。代码如下：

int count = 0;
public int count(int low, int high, String s, String a, String b) {
        int len = s.length();
        if(len > high){
            return 0;
        }
        if(len >= low){
            count++;
        }

        int left = count(low, high, s + a, a, b);
        int right = count(low, high, s + b, a, b);

        return count;
    }

public int countGoodStrings(int low, int high, int zero, int one) {
        String a = "0";
        String b = "1";
        a = a.repeat(zero);
        b = b.repeat(one);
        int[] dp = new int[high + 1];
        Arrays.fill(dp, -1);
        int ans = count(low, high, "", a, b);
        return ans;
}

记忆化递归优化方案 #

核心是用长度作为状态缓存结果，因为字符串的具体内容不影响后续操作，只需要关注当前长度就行，这样能避免大量重复计算。

优化后的代码 #

class Solution {
    private static final int MOD = 1_000_000_007;
    private int[] dp;
    private int low;
    private int high;
    private int zero;
    private int one;

    public int countGoodStrings(int low, int high, int zero, int one) {
        this.low = low;
        this.high = high;
        this.zero = zero;
        this.one = one;
        dp = new int[high + 1];
        // 初始化dp数组为-1，表示该长度还没计算过
        Arrays.fill(dp, -1);
        // 从空字符串（长度0）开始递归计算
        return dfs(0);
    }

    private int dfs(int currentLen) {
        // 超过最大长度，没有有效字符串，返回0
        if (currentLen > high) {
            return 0;
        }
        // 如果已经计算过这个长度的结果，直接返回缓存值
        if (dp[currentLen] != -1) {
            return dp[currentLen];
        }

        // 当前长度符合要求的话，先算上1个（当前字符串本身），否则为0
        int res = currentLen >= low ? 1 : 0;
        // 加上追加zero个0后能生成的有效字符串数
        res += dfs(currentLen + zero);
        res %= MOD; // 每次加完都取模，防止溢出
        // 加上追加one个1后能生成的有效字符串数
        res += dfs(currentLen + one);
        res %= MOD;

        // 把当前长度的结果缓存起来
        dp[currentLen] = res;
        return res;
    }
}

优化点说明 #

• 砍掉无效参数：不再传递字符串s、a、b，只传当前长度currentLen，因为后续操作只和长度有关，和具体字符无关，既省内存又减少参数传递开销。
• 缓存重复状态：用dp数组存储每个长度对应的有效字符串总数，下次遇到相同长度直接拿结果，时间复杂度从O(2^n)降到O(high)，彻底解决超时问题。
• 避免全局变量：递归函数直接返回当前长度能生成的有效字符串数，逻辑更清晰，不会出现全局变量被多次递归修改的问题。
• 大数取模：用1_000_000_007取模，防止数值过大导致整数溢出，这是算法题里的常规操作。

内容的提问来源于stack exchange，提问作者Apoorv Gupta