Java 记忆递归方法

Question

一段时间以来我一直在努力解决这个问题，但无法解决这个问题。

问题：给出下面的方法。用记忆优化它。

public static long cat(int n) {
    if (n == 0)
        return 1;
    long result = 0;
    for (int i = 0; i < n; i++) {
        result += cat(i) * cat(n - i - 1);
    }
    return result;
}

我尝试过的：

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;
}

我的想法是，内部 for 循环中所有计数的结果都将被保存。因此不必重复。

public static void main(String[] args) {
    System.out.println(cat(5)); //Prints 42
    System.out.println(memCat(5, new int[5 + 1])); //Prints 1 
}

我的眼睛和大脑都很累，所以这可能只是一个简单的错误。

Answer 1

您实施的问题在于您准备了 cache[]，但您从未使用它。这是解决方法，非常简单：

int result = cache[n];
if (result == 0) {
    for (int i = 0; i < n; i++) {
        result += memCat(i, cache) * memCat(n - i - 1, cache);
    }
    cache[n] = result;
}

现在cache的值是在之前计算过的时候返回的，因为result在进入条件之前被赋值为cache[n]。

Java 记忆递归方法

Java Memoization Recursive Method

java

memoization