凑指定总额最小硬币数的DP与递归Java代码错误排查求助

针对你遇到的最小硬币找零问题，我来帮你拆解两个版本代码的问题，并给出修正方案：

DP版本代码的问题与修复 #

你已经发现了核心错误之一：当当前硬币面值c[i-1] > j（即硬币面值超过当前目标总额）时，代码错误地将a[i][j]设为Integer.MAX_VALUE - total，但实际上这种情况应该继承不选当前硬币的最优解，也就是a[i-1][j]。这个错误导致部分场景下最优解被忽略，从而输出了错误的60而非正确的59。

另外，最后需要判断最终结果是否仍为我们定义的“无穷大”值，如果是则说明无法凑出总额，返回-1。

修正后的DP代码：

public static int mincoinDP(int[] c, int total) {
    int[][] a = new int[c.length + 1][total + 1];
    // 初始化：总额为0时，任何硬币组合都需要0枚
    for (int i = 0; i <= c.length; i++) {
        a[i][0] = 0;
    }
    // 定义安全的无穷大值，避免后续加1溢出
    int INF = Integer.MAX_VALUE - total;
    // 初始化：没有硬币时，非0总额都无法凑出
    for (int j = 1; j <= total; j++) {
        a[0][j] = INF;
    }
    for (int i = 1; i <= c.length; i++) {
        for (int j = 1; j <= total; j++) {
            if (c[i - 1] > j) {
                // 当前硬币用不了，直接用不选它的结果
                a[i][j] = a[i - 1][j];
            } else {
                // 选当前硬币（1+剩余总额的最小硬币数） vs 不选当前硬币，取最小值
                a[i][j] = Math.min(a[i - 1][j], 1 + a[i][j - c[i - 1]]);
            }
        }
    }
    // 若最终结果还是INF，说明无法凑出，返回-1
    return a[c.length][total] == INF ? -1 : a[c.length][total];
}

递归版本代码的问题与修复 #

你的递归代码有两个关键问题：

1. 当i >= c.length时返回Integer.MAX_VALUE，后续执行1 + 该值会直接溢出为负数（这就是你得到-2147483595的原因），所以需要返回一个不会触发溢出的“无穷大”值，比如Integer.MAX_VALUE - total。
2. 计算x（选当前硬币的情况）时，没有判断子问题是否有解，如果子问题返回的是“无穷大”，1 + 无穷大会溢出，所以要先判断子问题结果，只有有解时才加1。
3. 主函数需要最终判断结果是否为“无穷大”，如果是则返回-1，否则返回结果。

修正后的递归代码：

public static void main(String[] args) {
    int[] array = new int[] {31, 90, 8, 36};
    int total = 4759;
    int result = mincoin(array, total, 0);
    int INF = Integer.MAX_VALUE - total;
    // 判断是否无法凑出总额
    System.out.println(result == INF ? -1 : result);
}

public static int mincoin(int[] c, int total, int i) {
    if (total == 0) return 0;
    if (i >= c.length) return Integer.MAX_VALUE - total;
    int INF = Integer.MAX_VALUE - total;
    int x = INF;
    if (total - c[i] >= 0) {
        int subResult = mincoin(c, total - c[i], i);
        // 只有子问题有解时，才加1计算当前选择的硬币数
        if (subResult != INF) {
            x = 1 + subResult;
        }
    }
    int y = mincoin(c, total, i + 1);
    return Math.min(x, y);
}

关于“无穷大”处理的小建议 #

你提到不喜欢这种无穷大的处理方式，其实可以用更通用的安全值，比如final int INF = Integer.MAX_VALUE / 2，这样即使加1也不会溢出，适配各种总额场景，不需要依赖total计算。

内容的提问来源于stack exchange，提问作者Vipin