[LeetCode] Coin Change 2 JavaScript

문제

문제 LeetCode - Coin Change 2

amount 와 coins 가 주어진다.
예를 들어 amount = 5, coins = [1,2,5] 일 때 amount를 나타낼 수 있는 양이 몇 개인지를 묻는 문제이다. 동전의 양은 무한이다.
위 문제에서는 5 = 5, 5 = 2+2+1, 5 = 2+1+1+1, 5 = 1+1+1+1+1 로 4가지의 경우가 있다.

풀이

DP를 사용하면 풀 수 있다.
길이가 amount + 1인 배열을 만든다.
1부터 amount까지 각각의 만들 수 있는 가지 수를 구하면 된다.
위의 예로 설명하면
처음 상태는 [1, 0, 0, 0, 0, 0] 이다.
1만 사용해서 1,2,3,4,5를 모두 만들 수 있기 때문에 [1, 1, 1, 1, 1, 1] 로 만든다.
2를 사용해서 amount 각각을 만들려면 배열[amount - 2] 의 값이 존재한다면
배열[amount - 2]에서 2를 더하면 amount를 만들 수 있을 것이다.
각각의 값들을 더해주면 [1, 1, 2, 2, 3, 3] 가 된다.

5를 사용해서 amount 각각을 만들려면 배열[amount - 5]의 값을 더하면 될 것이다. amount -5 >= 0 이어야 하므로 마지막에 배열[0]의 값을 더해주면 된다.
그러면 [1, 1, 2, 2, 3, 4] 가 되고 답은 배열[amount] 가 된다.

JS 코드

const change = function (amount, coins) {
  const dp = new Array(amount + 1).fill(0); 
  // amount + 1의 길이를 가지는 배열을 만든 후 0으로 채운다.
  dp[0] = 1; 

  for (const coin of coins) {
    for (let i = coin; i <= amount; i++) {
      dp[i] += dp[i - coin]; // dp[i - coin]의 수만큼 더해준다.
    }
  }
  return dp[amount];
};