java - 使用记忆方法的二项式系数

Question

我编写了一个函数，它使用 memoizizion 方法递归地计算 n 和 k 的二项式系数项，OutOfBoundException当我执行时，我会很高兴听到一些关于我所犯错误的指示。谢谢你们。

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

Answer 1

一个非常简单的错误导致内部函数public static long binomial(int n, int k)更改中的此错误with ，我的意思是：nfork

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

是你正确的功能。