Binomical coefficient using the memoizazion methood

86 Views Asked by At

I wrote a function that recursively calculates the binomical coefficient term of n and k using the memoizazion methood, I get an OutOfBoundException when i execute, I'll be happy to hear some directions about the mistake I've done. Thank you all.

public class Binomial {

    public static void main(String[] args) {

        int n = Integer.parseInt(args[0]);
        int k = Integer.parseInt(args[1]);
        StdOut.print(binomial(n, k));
    }

    /**
     * Recursively calculates the binomical coefficient term of n and k using
     * the memoizazion methood
     *
     * @param n
     *            the upper nonnegative integer of the binomical coefficient
     * @param k
     *            the lower nonnegative integer of the binomical coefficient
     * @returns the computed binomical coefficient
     */
    public static long binomial(int n, int k) {
        long[][] mem = new long[n + 1][k + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                mem[i][j] = -1;
            }
        }
        return binomial(n, k, mem);
    }

    public static long binomial(int n, int k, long[][] mem) {
        if (k > n)
            return 0;
        if (k == 0 || n == 0)
            return 1;
        if (mem[n - 1][k] == -1) {
            mem[n - 1][k] = binomial(n - 1, k, mem);
        }
        if (mem[n - 1][k - 1] == -1) {
            mem[n - 1][k - 1] = binomial(n - 1, k - 1, mem);
        }
        return (mem[n - 1][k] + mem[n - 1][k - 1]);
    }
}
1

There are 1 best solutions below

0
On

A very simple mistake cause this error in function public static long binomial(int n, int k) change n in inner for with k, I mean :

public static long binomial(int n, int k) {
    long[][] mem = new long[n + 1][k + 1];
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            mem[i][j] = -1;
        }
    }
    return binomial(n, k, mem);
}

is your correct function.