0320._Coin_Change.md

322. Coin Change

难度: Medium

刷题内容

原题连接

• https://leetcode-cn.com/problems/coin-change/

内容描述

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

示例1：

 输入: coins = [1, 2, 5], amount = 11
 输出: 3 
 解释: 11 = 5 + 5 + 1

示例2：

 输入: coins = [2], amount = 3
 输出: -1

说明

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

解题方案

- 时间复杂度: O(N)- 空间复杂度: O(N)******

动态规划，思路参考：链接

代码：

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */

var coinChange = function(coins, amount) {
  // 自底向上的动态规划
  if(coins.length === 0){
    return -1;
  }
  
  // memo[n]的值： 表示的凑成总金额为n所需的最少的硬币个数
  let memo = Array.from({ length: amount+1 });
  memo[0] = 0;
  for(let i = 1; i <= amount; i++){
    let min = Number.MAX_VALUE;
    for(let j = 0; j < coins.length; j++){
      if(i - coins[j] >= 0 && memo[i-coins[j]] < min){
        min = memo[i-coins[j]] + 1;
      }
    }
    // memo[i] = (min == Integer.MAX_VALUE ? Integer.MAX_VALUE : min);
    memo[i] = min;
  }
  
  return memo[amount] === Number.MAX_VALUE ? -1 : memo[amount];
};