[LeetCode] 322. Coin Change

Problem

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Example 1:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

Example 3:

Input: coins = [1], amount = 0
Output: 0

Constraints:

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 2^31 - 1
• 0 <= amount <= 10^4

---

Solution

class Solution {
    public int coinChange(int[] coins, int amount) {
        int dp[] = new int[amount + 1];
        for (int i = 1; i <= amount; i++) { // i means amount that has to be filled
            int min = Integer.MAX_VALUE; // min means minimum num of coins to fill i
            for (int coin : coins)
               if (0 <= i - coin && dp[i - coin] != -1)
                   min = dp[i - coin] < min ? dp[i - coin] : min;
            // Set dp[i] to -1 if i (current amount) can not be reached by coins array
            dp[i] = min == Integer.MAX_VALUE ? -1 : 1 + min;
        }
        return dp[amount];
    }
}

Explanation

• amount보다 작은 크기의 amount를 채울 수 있는 가장 적은 coin의 개수를 구해보면 최종적으로 amount를 채울 수 있는 가장 적은 coin의 개수를 구할 수 있다.
• 위 사실을 구현하기 위해 배열 dp를 선언한다. 배열의 인덱스를 amount로 사용하기 위해 크기는 amount + 1로 지정한다.

  int dp[] = new int[amount + 1];
  

• 배열의 인덱스 i가 의미하는 amount를 채우기 위한 가장 적은 coin의 개수를 구하기 위해 for반복문을 선언한다.
• 그리고 가장 적은 coin의 개수를 구하기 위해 변수 min을 선언하고, 작은 값을 구하는 것이므로, int형 정수의 최대 값을 할당한다.

  for (int i = 1; i <= amount; i++) {
    int min = Integer.MAX_VALUE;
  }
  

• 첫 for반복문 내부에서 인덱스 i가 의미하는 amount를 채우기 위해 배열 conins의 요소를 이용해 가장 적은 coin의 개수를 의미하는 변수 min의 값을 구한다.

  for (int coin : coins)
   if (0 <= i - coin && dp[i - coin] != -1)
       min = dp[i - coin] < min ? dp[i - coin] : min;
  // Set dp[i] to -1 if i (current amount) can not be reached by coins array
  dp[i] = min == Integer.MAX_VALUE ? -1 : 1 + min;
  

• amount를 채울 수 있는 가장 적은 coni의 개수를 의미하는 배열 dp의 마지막 요소를 반환한다.

  return dp[amount];