322. 零钱兑换

链接：https://leetcode-cn.com/problems/coin-change/

感想

看了半天题解，才理解。估计过一个月再来做，还是做不出来，我一定是个废物。

解法1：动态规划

（1）第一步：定义数组元素的含义

用一个一维数组来表示当前构成i的面额，最小需要多少枚硬币

（2）第二步：找出数组元素之间的关系式

dp[i] = min(dp[i], dp[i - conis[j]] + 1)

这个动态规划方程不太好想，当前dp[i]，枚举的最后一枚硬币的面值是coins[j]，需要取conis[j-1], coins[j-2], ...coins[0]的最小值，再加上当前这枚硬币的数量

（3）第三步：找出初始值

当i === 0时，无法用硬币组成，为0，当i < 0时忽略dp[i]

var coinChange = function (coins, amount) {
  const len = coins.length,
    dp = [0];

  for (let i = 1; i <= amount; i++) {
    dp[i] = amount + 1;
    for (let j = 0; j < len; j++) {
      if (coins[j] <= i) {
        dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
      }
    }
  }

  return dp[amount] > amount ? -1 : dp[amount];
};

• 时间复杂度：${O(S * N)}$，S为金额，N为面额数
• 空间复杂度：${O(S)}$
• 执行用时：96ms, 在所有JavaScript提交中击败了100%的用户，内存消耗：43.3MB，在所有JavaScript提交中击败了37%的用户

解法2：记忆化搜索

解法1是从下向上的思路，现在从上之下考虑，需要利用递归

判断金额凑不出的小技巧：先初始化DP table各个元素为amount + 1（代表不可能存在的情况），在遍历时如果金额凑不出则不更新，于是若最后结果仍然是amount + 1，则表示金额凑不出

var coinChange = function (coins, amount) {
  if (amount < 1) {
    return 0;
  }

  return change(coins, amount);
};

function change(coins, amount, cache = {}) {
  // 结束条件1：无法凑成对应的金额
  if (amount < 0) {
    return -1;
  }
  // 结束条件2：凑成了想要的结果，直接返回
  if (amount === 0) {
    return 0;
  }
  // 以前计算过的值也直接返回
  if (cache[amount]) {
    return cache[amount];
  }

  // 填充一个比当前金额更大的值，用 Infinity 也可以
  let min = amount + 1;

  // 去遍历所有的硬币
  for (let i = 0, len = coins.length; i < len; i++) {
    // 获得一个结果
    const temp = change(coins, amount - coins[i], cache);
    // 如果符合条件，并且比当前金额小，才可以更新
    if (temp >= 0 && temp < min) {
      min = temp + 1;
    }
  }
  cache[amount] = min === amount + 1 ? -1 : min;
  return cache[amount];
}

• 时间复杂度：${O(S * N)}$，S为金额，N为面额数
• 空间复杂度：${O(S)}$
• 执行用时：140ms, 在所有JavaScript提交中击败了59%的用户，内存消耗：44.5MB，在所有JavaScript提交中击败了14%的用户