Java Memoization Recursive Method

Question

Been trying to figure out this issue for a while but can't get my head around it.

Question: Given the method below. Optimise it with memoization.

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

What I have tried:

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

My idea behind this is that as the result for all the counts in the inner for loop will be saved. So it does not have to be repeated.

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

My eyes and brain are tired so it may just be a simple mistake.

Answer 1

The problem with your implementation is that you prepare cache[], but you never use it. Here is the fix, it's rather straightforward:

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

Now the value of cache is returned when it has been computed before, because result is assigned a value of cache[n] before entering the conditional.