java - Java 中的分区函数 NullPointerException

Question

我正在实现 Partition function ，可以看到第一个函数中long(or int)的返回值是没有问题的。

public static long p(int n) {
        long[] ways = new long[n + 1];
        ways[0] = 1;
        int[] coins = new int[n];
        for(int i = 0; i < n; i++)
            coins[i] = i + 1;   
        for(int coin : coins) {
            for(int j = coin; j <= n; j++) {
                ways[j] += ways[j - coin];
            }
        }
        return ways[n];
    }

它返回正确的值。但是当我用BigInteger值实现时(当输入n很大时，返回值超出了Long的范围)，结果出错了，出现了java.lang.NullPointerException。我找不到我做错的地方。 有 bug 的函数如下:

    public static BigInteger p(int n) {
            BigInteger[] ways = new BigInteger[n + 1];
//initial the BigInteger[] ways------> Additional question: Is it necessary?
            ways[0] = BigInteger.ONE;
            for(int i = 1; i < n; i++)
                ways[i] = BigInteger.ONE; // --update-- Here should be initialed with BigInteger.ZERO, not ONE!
            int[] coins = new int[n];
            for(int i = 0; i < n; i++)
                coins[i] = i + 1;
            for(int coin : coins) {
                for(int j = coin; j <= n; j++) {
                    BigInteger temp = ways[j].add(ways[j - coin]);
                    ways[j] = temp;
                }
            }
            return ways[n];
        }

任何回复将不胜感激!

Answer 1

您的 ways-array 的大小为 n+1。在你的 for 循环中，你从 i = 1 < n 开始。不应该是

代替

for(int i = 1; i < n; i++)
        ways[i] = BigInteger.ONE;

你应该做的

for(int i = 1; i < n+1; i++)
        ways[i] = BigInteger.ONE;