LeetCode / Dynamic Programming / 322번 / Coin Change / JS

< 문제 바로가기 >

Coin Change - LeetCode

 

< 문제 간단설명 >

주어진 amount의 값을 만들기 위해 coins 배열에 담겨있는 coin의 동전을 최소 몇 개 써야하는지 반환하는 문제이다. 만약 coins의 동전들로 만들 수 없는 값이라면 -1을 반환한다.

 

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function (coins, amount) {
  let dp = Array.from({ length: amount + 1 }, () => Infinity);
  dp[0] = 0; // 0원은 0개의 동전이 필요

  for (const COIN of coins) {
    for (let i = COIN; i <= amount; i += 1) {
      // i원은 (i - COIN)원 보다 COIN원의 동전 1개를 더 사용
      // 혹은 이미 더 적은 동전을 사용해서 만들 수 있다면 그대로
      dp[i] = Math.min(dp[i], dp[i - COIN] + 1);
    }
  }

  return dp[amount] === Infinity ? -1 : dp[amount];
};