在 javascript 中调试 leetcode 解决方案 - 硬币兑换，

Question

我解决了一个leetcode问题，对我来说看起来是正确的，但事实并非如此，我无法理解为什么它是错误的。有人可以告诉我为什么我的解决方案不起作用 下面是问题

您将获得一个表示不同面额硬币的整数数组硬币和一个表示总金额的整数金额。返回组成该金额所需的最少硬币数量。如果该金额不能由任何硬币组合组成，则返回 -1。 您可以假设您拥有无限数量的每种硬币。

这是我的解决方案

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

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

  if (amount === 0) {
    cache[amount] = coinUsedTillNow
    return coinUsedTillNow
  }

  if (amount < 0) {
    return -1
  }

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

  cache[amount] = -1
  return -1

Answer 1

当正确的做法始终是首先使用最高面额的硬币时，您的代码可以完美运行。

例如，如果面额是

[10, 5, 2, 1]

，并且目标金额大于

10

，我应该始终使用

10

硬币至少一次。

但是，如果面额是

[100, 57, 50, 1]

，并且目标金额是

107

，那么我不应该使用

100

硬币。

因此，您的代码的问题在于它过早地放弃了搜索（您的

for

循环）。