最小硬币数量

如果不可能的话,我尝试打印最小数量的硬币来进行更改-1

在这段代码中,变量int[]c(coins array)有一些面额,我可以用这些面额计算总数。

总利息有总金额,我需要使用硬币(无限供应)

    public static int mincoinDP(int[] c, int total) {
        int[][] a = new int[c.length + 1][total + 1];

        for (int i = 0; i <= c.length; i++) {
            a[i][0] = 0;
        }
        for (int j = 1; j <= total; j++) {
            a[0][j] = Integer.MAX_VALUE - total;
        }

        for (int i = 1; i <= c.length; i++) {
            for (int j = 1; j <= total; j++) {
                if (c[i - 1] > j) {
                    a[i][j] = Integer.MAX_VALUE - total;
                } else {
                    a[i][j] = Math.min(a[i - 1][j], 1 + a[i][j - c[i - 1]]);
                }
            }
        }

        return a[c.length][total];
    }

求和:4759,数组:31 90 8 36正确输出为:59 我的输出是:60

代码有什么问题?

下面是我的递归解决方案,尝试在dp解决方案中应用相同的逻辑。这里的逻辑似乎也有问题。对于相同的输入,它打印-2147483595

    public static void main(String[] args) {
        int[] array = new int[] {31, 90, 8, 36};
        System.out.println(mincoin(array, 4759, 0));
    }

    public static int mincoin(int[] c, int total, int i) {

        if (total == 0) return 0;
        if (i >= c.length) return Integer.MAX_VALUE;


        int x = Integer.MAX_VALUE, y = Integer.MAX_VALUE;

        if (total - c[i] >= 0) {
            x = 1 + mincoin(c, total - c[i], i);
        }
        y = mincoin(c, total, i + 1);

        return Math.min(x, y);
    }

编辑:代码中的问题有:

1. dp版本:如果(c[i-1]>j),当解决方案不是 可能选择这个硬币:这里我们应该接受没有 这枚硬币是一枚
2. 递归版本:如果(i>=c.length), 当我们在这个位置没有硬币的时候,这是终止条件, 这里我们应该返回无穷大(integer.max_值)和 为避免整数溢出,返回integer.max_value-total。

虽然我不喜欢这个版本的无穷大,但除了这里没有看到任何好的方式。