66.零钱兑换

day15: 322. 零钱兑换（中等）
考点：动态规划
思路：也是所谓的填表格，但是要找好填表格的角度。
日常思维：循环所有数组，用目标元素除以当前元素的值存为结果，如果整除则存入，如果没有整除则查看余数中的值是否存在于当前数组中，存在则返回商+余数的硬币个数，每次求最小值。
动态规划：可以将其划分成当总数为[1,amount]时，用[1,2,5]硬币分别需要多少个可以将其填满，将求得的结果缓存。
参考leecode

image.png

var coinChange = function (coins, amount) {
  //amount为0直接返回
  if (amount == 0) return 0;
  //没有零钱
  if (coins.length == 0) return -1;

  let dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  //计算使用icon找零i需要多少个硬币
  for (let i = 0; i <= amount; i++) {
    for (let icon of coins) {
      //i-icon<0说明不够找，还用初始化的值。否则说明够找
      if (i - icon >= 0) {
        dp[i] = Math.min(dp[i], dp[i - icon] + 1);
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
};

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