调试LeetCode Coin Change问题的JavaScript解决方案

问题描述 #

给定一个表示不同面额硬币的整数数组coins和一个表示总金额的整数amount。返回凑成该金额所需的最少硬币个数。如果无法用给定硬币凑出该金额，返回-1。假设每种硬币的数量是无限的。

你的解决方案 #

var coinChange = function (coins, amount) {
coins = coins.sort((a, b) => b - a)
let cache = {}
let result = coinChangeHelper(coins, amount, 0, cache)
console.log(cache)
return result
};

var coinChangeHelper = (coins, amount, coinUsedTillNow, cache) => {
    if (cache[amount] !== undefined) {
        return cache[amount]
}

if (amount === 0) {
    return coinUsedTillNow
}

if (amount < 0) {
    return -1
}

let result = Infinity
for (let i = 0; i < coins.length; i++) {
    let temp = coinChangeHelper(coins, amount - coins[i], coinUsedTillNow + 1, cache)
    if(temp === -1)
        continue
    result = Math.min(result,temp)
}
if (result !== Infinity) {
    cache[amount] = result
    return result
}

cache[amount] = -1
return -1
}

错误原因分析 #

你的解法核心问题出在缓存逻辑和递归参数的绑定错误：

• 你用cache[amount]存储凑成amount的结果，但递归函数返回的是coinUsedTillNow + 后续递归的硬币数，这导致缓存的值和当前递归层级的coinUsedTillNow强绑定，而非amount对应的独立最少硬币数。
• 举个实际例子：假设coins=[2,1]，amount=3。当走路径3→1时，coinUsedTillNow=1，递归处理amount=1会返回2（1+1），此时cache[1]=2。但如果走另一条路径3→2→1，处理amount=1时直接取缓存的2，加上当前的coinUsedTillNow=2，得到4，这明显不是凑成1的最少硬币数（实际是1）。
• 另外，对coins降序排序的操作没有实际优化作用，反而可能让某些正确路径被晚处理，但这不是核心错误。

修正思路与代码 #

调整递归逻辑，让函数直接返回凑成当前amount所需的最少硬币数，而非基于coinUsedTillNow的累加值，缓存内容也变为独立的最少硬币数：

var coinChange = function(coins, amount) {
    let cache = {};
    const result = coinChangeHelper(coins, amount, cache);
    return result === Infinity ? -1 : result;
};

var coinChangeHelper = function(coins, amount, cache) {
    if (cache[amount] !== undefined) {
        return cache[amount];
    }
    if (amount === 0) {
        return 0; // 凑0元需要0个硬币
    }
    if (amount < 0) {
        return Infinity; // 用Infinity表示不可凑出，后续方便取最小值
    }
    let minCoins = Infinity;
    for (let coin of coins) {
        const subResult = coinChangeHelper(coins, amount - coin, cache);
        if (subResult !== Infinity) {
            minCoins = Math.min(minCoins, subResult + 1);
        }
    }
    cache[amount] = minCoins;
    return minCoins;
};

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