Lstmxx的空间

322. 零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回  -1 。

你可以认为每种硬币的数量是无限的。

链接

function coinChange(coins: number[], amount: number): number {
  const dpTable: Record<number, number> = {};
  function dp(n) {
    if (dpTable[n]) return dpTable[n];
    if (n === 0) return 0;
    if (n < 0) return -1;
    let res = Number.POSITIVE_INFINITY;
    for (let i = 0; i < coins.length; i++) {
      const c = dp(n - coins[i]);
      if (c === -1) continue;
      res = Math.min(res, c + 1);
    }
    dpTable[n] = res === Number.POSITIVE_INFINITY ? -1 : res;
    return dpTable[n];
  }
  return dp(amount);
}