[리트코드] 322. Coin Change




322. Coin Change

리트코드 문제 바로가기

나의 풀이

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function (coins, amount) {
  const dp = new Array(amount+1).fill(Infinity)
  dp[0] = 0

  for(let i = 1; i<dp.length; i++){
    coins.forEach(coin => {
      if(i-coin >= 0) dp[i] = Math.min(dp[i], dp[i-coin]) + 1
    })
  }
  return dp[amount] === Infinity ? -1 : dp[amount]
};

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



f(n) = Math.min(f(n-2) + f(n-3) + f(n-5)) + 1
dp 접근법에 익숙해지고 최대한 다양한 문제를 접하자