0

我正在实现Partition函数，你可以看到第一个函数中long(或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];
        }

任何回复将不胜感激！

4

2 回答 2

2

您的方式数组的大小为 n+1。在你的 for 循环中，你从 i = 1 < n 开始。它不应该是 < n+1 吗？

代替

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

你应该做

for(int i = 1; i < n+1; i++)
        ways[i] = BigInteger.ONE;
于 2013-07-30T12:03:08.983 回答
1

您必须在 for 循环中将 n 更改为 n+1：

 for(int i = 1; i < n; i++)
        ways[i] = BigInteger.ONE;
于 2013-07-30T12:06:18.347 回答