[322] 零钱兑换

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

示例 1:

输入: coins = [1, 2, 5], amount = 11

输出: 3

解释: 11 = 5 + 5 + 1

示例 2:

输入: coins = [2], amount = 3

输出: -1

说明:

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

带回溯的贪心法

这道题粗略一看，一般都会想到使用贪心法来解。每次选取尽可能多的最大面额硬币去逼近总金额，之后使用第二大面额硬币逼近，直到面值和等于总金额或者所有可用硬币种类逼近完后停止。

但是这样做是不对的。试着考虑这样一种情况，coins=[1, 6, 10], amount=18。很明显6+6+6的组合是要优于10+6+1+1的。这就是我们使用贪心法时经常会遇到的：贪心法求得的时局部最优解，而局部最优不一定等于全局最优。

因此我们还得对该算法进行进一步的改进。现在将最大面额的硬币减少一枚，剩余值从第二大面额的硬币开始逼近，直到得到该种情况下的最优解，再继续减少一枚当前最大面额的硬币，从当前第二大面额的硬币开始逼近……直到最后只有最小面额的硬币逼近取得的最优解。将这些局部最优解取出取最小值，即可得到全局最优解了。

不难看出，这样的做法实际上就是回溯上一层的一次操作，向另一个分支遍历。实际上就是一次数的深度优先遍历（DFS）了。

当然，这样做虽然能够顺利得出答案，但是时间复杂度会非常高，因此我们需要作出优化。那么最简单的优化就是，当每次贪心求局部最优的过程中，若当前逼近硬币数已经超过了其他情况下的局部最优解了，那么显然该次贪心算法不是全局最优解，将后面的运算全部剪枝即可。

let res = Number.MAX_SAFE_INTEGER;

var coinChange = function(coins, amount) {
  if (amount === 0) return 0;
  // 从大到小排序
  coins.sort((a, b) => b - a);

  dfs(coins, 0, amount, 0);
  return res < Number.MAX_SAFE_INTEGER ? res : -1;
};

function dfs(coins, index, amount, count) {
  if (index >= coins.length) return;

  // 当剩余值为0,说明找到了一组最优解
  if (amount === 0) {
    res = Math.min(count, res);
    return;
  }

  for (let i = Math.floor(amount / coins[index]); i >= 0; i--) {
    const newCount = count + i;
    const rest = amount - i * coins[index];

    // 当前硬币数已经超过最优解了，剪枝
    if (newCount >= res) break;

    dfs(coins, index + 1, rest, newCount);
  }
}

动态规划

当然，我们也可以用动态规划的思路来解决这个问题，可以将其转化为一个不限制背包容量的背包问题。设立二维数组，coins[i]为硬币的种类，j为背包容量(在本题即为目标金额)，dp[i][j]表示当目标金额amount为j时，最少需要的coins[i]种类的硬币多少个。

经过上面的分析可以得知，我们每一次做选择时，对于任意一枚硬币时都有取或者不取两种情况。当取该枚硬币时，最少硬币的情况应该等于组成j-coins[i]元的最少硬币组成个数 + 1，即dp[i][j] = dp[i, j-coins[i] + 1；当不取该枚硬币时，相当于没有遍历过i这一位置，因此该情况下个数等价于dp[i-1, j]时的个数。

这里为dp数组设置最大初始值是amount+1，是因为硬币是正整数，那么组成amount的硬币个数就不可能超过amount个1元硬币。

状态转移方程：dp[i, j] = min(dp[i - 1, j], dp[i, j - coins[i]] + 1)

var coinChange = function(coins, amount) {
  // 初始化dp二维数组与第一行、第一列的值
  const dp = new Array(coins.length).fill(0).map(x => new Array(amount + 1).fill(Number.MAX_SAFE_INTEGER));
  for (let i = 0; i < dp.length; i++) {
    dp[i][0] = 0;
  }
  for (let i = 0; i < dp[0].length; i++) {
    dp[0][i] = i % coins[0] === 0 ? Math.floor(i / coins[0]) : Number.MAX_SAFE_INTEGER;
  }

  for (let j = 1; j <= amount; j++) {
    for (let i = 1; i < coins.length; i++) {
      if (j >= coins[i]) {
        dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - coins[i]] + 1);
      } else {
        dp[i][j] = dp[i - 1][j];
      }
    }
  }
  return dp[coins.length - 1][amount] < Number.MAX_SAFE_INTEGER ? dp[coins.length - 1][amount] : -1;
};

我们也可以用一维表代替二维表，从而节省空间复杂度。此时dp[i]表示，当目标金额为i时的硬币组成最小个数。

举个例子来说，假设 coins = [1, 2, 5, ...], 那么，该算法的递推式为：min(f(n-1), f(n-2), f(n-5), ...) + 1。(若n < i 则f(n-i)不计入在内)

因此对每一种硬币coin，有：dp[i] = min(dp[i], dp[i - coin] + 1)

function coinChange(coins: number[], amount: number): number {
  const dp = Array(amount + 1).fill(Number.MAX_SAFE_INTEGER);
  dp[0] = 0;

  // Sn = MIN(S[n-coin] + 1)
  for (let i = 1; i <= amount; i++) {
    coins.forEach(coin => {
      if (i - coin >= 0) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    });
  }
  return dp[amount] === Number.MAX_SAFE_INTEGER ? -1 : dp[amount];
}