LeetCode 322 - Coin Change

Coin Change - LeetCode

 

amount를 만드는데 필요한 최소 코인 개수를 찾아야 한다.

coins = [1, 2, 5], amount = 11 일 때

11 = 5 + 5 + 1 이 최소이다. 답은 3이다.

coins = [2], amount = 3 일 때

3은 2를 통해 만들 수 없기 때문에 -1이 답니다.

coins = [1], amount = 0이면 0개를 사용하면 되기 때문에 답은 0이다.

우선 greedy를 고려해 볼 수 있지만 각 동전은 대체가 불가능하기 때문에 최적해를 보장할 수 없다.

dp를 생각해 보자.

dp [i] = i원을 만드는데 필요한 최소 동전 개수이다.

첫 번째 예시에서 dp [11] = min(dp [6], dp [9], dp [10]) + 1 이렇게 된다.

정리하자면 dp [i] = min(dp [i], dp [i-coin] + 1), for coin in coins, dp [0] = 0이 된다.

class Solution {
    public int coinChange(int[] coins, int amount) {
        int INF = Integer.MAX_VALUE;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, INF);
        dp[0] = 0;

        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (i - coin >= 0 && dp[i-coin] != INF) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1); 
                }
            }
        }

        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
}