零钱兑换问题递归DP实现错误排查：为何计算结果不符？

我帮你找到代码里的问题啦！你的递归DP思路方向是对的，但有一个关键判断逻辑写错了，导致漏掉了部分可行的组合方式。

你的核心思路是通过递归拆分“选当前硬币”和“不选当前硬币”两种场景，并用备忘录缓存结果避免重复计算，这个方向没问题。但问题出在这一行代码：

if(n < c[i]) return 0;

为什么这行代码错了？ #

当剩余金额n小于当前硬币面额c[i]时，你直接返回0，相当于判定“没有任何方式凑出n”，但实际上正确的逻辑应该是不能选当前硬币，直接尝试下一个面额的硬币，而不是直接判定无解。

比如在你提到的测试用例（面额{2,5,3,6}凑10元）中：

• 当递归到n=3、i=1（当前硬币是5）时，3<5，你的代码直接返回0，但实际上我们可以跳过5，去尝试后面的3硬币，这是能凑出3元的（选一个3）。这个遗漏直接导致总方式数少了1，所以代码返回4而不是正确的5。

修正方案 #

把这行错误的判断改成：当n < c[i]时，只能选择不选当前硬币，返回跳过当前硬币后的递归结果：

if(n < c[i]) return fun(n, c, i+1, memo);

修正后的完整代码 #

import java.util.HashMap;
import java.util.Map;

public class CoinChange {
    public static long getWays(long n, long[] c) {
        Map<String, Long> map = new HashMap<>();
        return fun(n, c, 0, map);
    }

    public static long fun(long n, long[] c, int i, Map<String, Long> memo){
        if(n == 0) return 1;
        if(i >= c.length) return 0;
        // 修正后的判断逻辑
        if(n < c[i]) return fun(n, c, i+1, memo);
        
        String key = n + "_" + i;
        if(memo.containsKey(key)) return memo.get(key);
        
        long ways = fun(n, c, i+1, memo) + fun(n-c[i], c, i, memo);
        memo.put(key, ways);
        return ways;
    }

    public static void main(String[] args) {
        // 测试用例：面额{2,5,3,6}凑10元，应该返回5
        long[] coins = {2,5,3,6};
        System.out.println(getWays(10, coins)); // 输出5，结果正确
    }
}

额外小提示 #

硬币数组的顺序不会影响最终结果，因为我们是按顺序逐个处理每个硬币，不管顺序如何都会覆盖所有组合。如果先对硬币数组排序，可能会减少一些递归分支，但不是必须的——修正上述错误后代码已经能正确运行。

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