Java自上而下DP实现零钱兑换问题仅部分测试用例通过求解

你代码的核心问题有两个：

1. 整数溢出问题：你用Integer.MAX_VALUE作为无法凑出金额的标记，当子问题返回Integer.MAX_VALUE时，直接执行+1操作会触发整数溢出，结果变为负的Integer.MIN_VALUE，后续Math.min比较时会把这个非法值当成更小的合法结果，导致逻辑完全错误，这就是你边界情况处理失败的核心原因。
2. 多余的start参数（可选优化）：你照搬了组合求和类问题的剪枝逻辑，但零钱兑换求最少硬币数的场景下，start参数完全没有必要，即使保留也不影响结果，但去掉后代码逻辑更清晰，也不会出现漏解的情况。

比如测试用例coins = [2], amount = 3：

• 递归计算amount=3时，子问题amount=1没有合法解，返回Integer.MAX_VALUE
• 直接执行Integer.MAX_VALUE + 1得到Integer.MIN_VALUE，错误更新dp[3] = Integer.MIN_VALUE
• 最终主函数判断res == Integer.MAX_VALUE不成立，不会返回-1，而是返回错误的负数结果。

import java.util.Arrays;

public int coinChange(int[] coins, int amount) {
    if (amount == 0)
        return 0;
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    // 提前初始化基础状态
    dp[0] = 0;
    int res = helper(coins, dp, amount);
    return res == Integer.MAX_VALUE ? -1 : res;
}

public int helper(int[] coins, int[] dp, int amount) {
    // 已经计算过的状态直接返回
    if (dp[amount] != Integer.MAX_VALUE)
        return dp[amount];
    for (int i = 0; i < coins.length; ++i) {
        if (coins[i] <= amount) {
            // 先判断子问题是否有合法解，再更新当前状态，避免溢出
            int subRes = helper(coins, dp, amount - coins[i]);
            if (subRes != Integer.MAX_VALUE) {
                dp[amount] = Math.min(dp[amount], subRes + 1);
            }
        }
    }
    return dp[amount];
}

• 去掉了多余的start参数，每次递归遍历所有硬币，保证不会漏解；如果你要保留start参数做剪枝减少重复计算，只要加上子问题结果的合法性判断，代码也能正常运行
• 增加了子问题结果的合法性判断，只有子问题能凑出金额时，才更新当前状态，完全避免了整数溢出问题
• 提前初始化dp[0] = 0，简化了递归终止逻辑

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