LeetCode最小硬币找零一维数组自上而下DP实现问题排查求助

核心错误原因 #

你的代码本质问题是记忆化缓存的定义和递归逻辑不匹配，破坏了动态规划子问题的独立性：

• 你定义的dp[sum]本意是存储凑出金额sum需要的最少硬币数，是和当前路径已使用硬币数无关的全局最优解
• 但你在递归函数中传入了路径相关的curCoins参数，第一次计算dp[sum]时会把当前路径的结果存进去，而这个结果大概率不是全局最优，后续所有访问到dp[sum]的逻辑都会直接返回这个错误值，导致最终结果偏大

其他次要问题 #

你当前的递归分支逻辑是「选当前索引的硬币/不选当前索引的硬币，跳到下一个更小面值」，本质是按硬币顺序的贪心试探逻辑，不是标准的无限背包自上而下DP逻辑，虽然理论上可以覆盖所有组合，但结合错误的缓存逻辑会放大误差。

修正方案 #

把递归函数的返回值定义为「凑出参数传入的sum需要的最少硬币数」，去掉路径相关的curCoins参数，重新设计缓存逻辑即可：

int fncUtil(int dp[], int a[], int sum) {
    if(sum == 0) {
        return 0;
    }
    if(sum < 0) {
        return Integer.MAX_VALUE;
    }
    // 已计算过的子问题直接返回缓存值
    if(dp[sum] != 0) {
        return dp[sum];
    }
    int min = Integer.MAX_VALUE;
    // 遍历所有硬币，每个都可重复选择，匹配无限使用规则
    for(int coin : a) {
        int subRes = fncUtil(dp, a, sum - coin);
        if(subRes != Integer.MAX_VALUE) {
            min = Math.min(min, subRes + 1);
        }
    }
    dp[sum] = min;
    return min;
}
public int coinChange(int[] a, int sum) {
    if(sum == 0) return 0;
    int dp[] = new int[sum+1];
    int minCoins = fncUtil(dp, a, sum);
    return minCoins == Integer.MAX_VALUE ? -1 : minCoins;
}

如果要保留你原来的「按索引选/不选硬币」的分支逻辑，需要把缓存改为二维数组存储「剩余硬币索引+剩余金额」对应的最少硬币数，效率低于上述实现。

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