硬币兑换 - 测试用例失败

Question

问题是这样的：

您将获得一个表示不同面额硬币的整数数组硬币和一个表示总金额的整数金额。

返回弥补该金额所需的最少数量的硬币。如果任何硬币组合都无法弥补该金额，则返回 -1。

您可能会假设您拥有无限数量的每种硬币。

示例1：

输入：硬币 = [1,2,5]，金额 = 11 输出：3 解释：11 = 5 + 5 + 1

这是我尝试解决的方法。但对于这个测试用例它失败了： [195,265,404,396]，金额 3239 感谢任何帮助。

var coinChange = function(coins, amount) {
    let ans = Infinity;
    var helper = function(coins, amount, index=0, coinsNeeded = 0){
        if(amount === 0){
            ans = Math.min(ans, coinsNeeded);
            return;
        }
        if(index >= coins.length) return;

        if(coins[index] > amount) return;
        if(amount % coins[index] === 0){
            ans = Math.min(ans, coinsNeeded + amount / coins[index]);
        }

        helper(coins, amount-coins[index], index, coinsNeeded+1);
        helper(coins, amount, index+1, coinsNeeded);
        
    }

    helper(coins, amount);

    return ans === Infinity ? -1 : ans;
    
};

console.log(coinChange([1,2,5], 11))

Answer 1

我不确定你做错了什么，但这也许有点帮助。最简单的方法（假设没有性能要求）是计算达到请求的金额所需的硬币数量。 在您的情况下，从 0 到 3239。 下一步是迭代给定的金额并为每个金额计算最小值。 对于给定的金额，您迭代给定的硬币并尝试从金额中减去该硬币，如果结果大于 -1，那么您就知道金额减去当前硬币值的解决方案可以增加 1 个硬币。但在保留这个数字之前，您必须检查我们是否已经有该数量的数字，并且只有在新数字较小时才保留新数字（因为我们正在寻找最少数量的硬币）。

function coinChange(coins, amount) {
    // Initialize minCoinsForAmoint array with a large value (infinity)
    let minCoinsForAmoint = new Array(amount + 1).fill(Infinity);
    minCoinsForAmoint[0] = 0;  // Base case: 0 coins to make amount 0

    // Iterate over all amounts from 1 to the target amount
    for (let i = 1; i <= amount; i++) {
        // Try using each coin to update minCoinsForAmoint[i]
        for (let coin of coins) {
            if (i - coin >= 0) {
                minCoinsForAmoint[i] = Math.min(minCoinsForAmoint[i], minCoinsForAmoint[i - coin] + 1);
            }
        }
    }

    // If minCoinsForAmoint[amount] is still infinity, it means it's impossible to form that amount
    return minCoinsForAmoint[amount] === Infinity ? -1 : minCoinsForAmoint[amount];
}

const coins = [195,265,404,396];
const amount = 3239;
console.log(coinChange(coins, amount));