卡特兰数递归方法的记忆化优化问题排查

我看到你在给卡特兰数递归方法做记忆化优化时遇到了输出错误的问题，原方法计算cat(5)返回42，但你的memCat实现返回1，咱们来一步步找出问题并修复它。

核心错误：缓存命中时返回了初始值而非缓存值 #

看你的memCat代码，这里有个关键逻辑漏洞：

private static int memCat(int n, int[] cache) {
    if (n == 0) {
        return 1;
    }
    int result = 0;
    if (cache[n] == 0) {
        for (int i = 0; i < n; i++) {
            result += memCat(i, cache) * memCat(n - i - 1, cache);
        }
        cache[n] = result;
    }
    return result; // 这里错了！当cache[n]不为0时，result还是初始的0
}

当某个n的缓存值已经存在（cache[n] != 0），代码会跳过循环直接返回result，但result初始化为0，这就导致后续重复调用该n时返回错误的0值，进而让整个计算结果彻底出错。

举个例子：第一次计算memCat(1)时，cache[1]会被设为1并返回1；但第二次调用memCat(1)时，cache[1] != 0，代码跳过循环，直接返回初始的0，这会让依赖memCat(1)的所有后续计算都出错，最终导致memCat(5)返回错误结果。

另外还有两个小问题需要注意：

• 卡特兰数增长很快，int类型会很快溢出（n=20时卡特兰数就超过int最大值了），所以应该用long类型避免溢出，和原方法保持一致。
• cache[0]没有被初始化，虽然n=0直接返回1，但为了缓存逻辑的完整性，最好也把cache[0]设为1。

修复后的代码 #

下面是修正后的记忆化实现，解决了上述所有问题：

private static long memCat(int n, long[] cache) {
    // 处理n=0的情况，同时初始化缓存
    if (n == 0) {
        cache[0] = 1;
        return cache[0];
    }
    // 缓存命中直接返回
    if (cache[n] != 0) {
        return cache[n];
    }
    long result = 0;
    for (int i = 0; i < n; i++) {
        result += memCat(i, cache) * memCat(n - i - 1, cache);
    }
    // 将计算结果存入缓存
    cache[n] = result;
    return result;
}

使用示例 #

调用时需要创建足够大小的缓存数组（大小为n+1，因为卡特兰数从n=0开始）：

public static void main(String[] args) {
    int n = 5;
    long[] cache = new long[n + 1];
    System.out.println(memCat(n, cache)); // 输出42，和原方法一致
}

修复说明 #

1. 修正缓存命中逻辑：现在先检查缓存，如果cache[n]不为0直接返回，避免返回初始的0值。
2. 改用long类型：防止卡特兰数增大后溢出，和原方法的返回类型保持一致。
3. 初始化cache[0]：让缓存逻辑更完整，避免潜在的问题。

这样修改后，记忆化优化就能正常工作，既避免了重复计算，又保证了结果的正确性。

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