LeetCode 322 - Coin Change (Medium)

문제

LeetCode - 322번

풀이 과정

오랜만에 풀어보는 동적 계획법 문제입니다.

dp[x] = x 원을 만들기 위한 최소 동전의 개수 라고 정의한다면 다음과 같은 점화식을 얻을 수 있습니다.

dp[x] = for all coins, min{ dp[x - coins[i]] }

이때 i 는 i 번째 동전을 의미합니다.

코드

/**
 * @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 money = 1; money <= amount; money++) {
    for (let i = 0; i < coins.length; i++) {
      if (coins[i] <= money) {
        dp[money] = Math.min(dp[money], dp[money - coins[i]] + 1);
      }
    }
  }

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