[LeetCode] 322. Coin Change - 동적계획법(Dynamic Programming) JAVA

https://leetcode.com/problems/coin-change/

코드설명

동적계획법(Dynamic Programming) 을 활용합니다.

 

일반적으로 최소개수를 구하는 문제보다는, 동전의 최대개수를 구하는 문제가 많습니다.

하지만, 결국 같은 문제입니다.

 

최대개수를 구할때는 0으로 초기값을 설정하고, MAX값으로 갱신하면 되고,

최소개수를 구할때는 amount로 초기값을 설정하고, MIN 값으로 갱신하면됩니다.

이때, 만약 반환값이 초기값과 같다면, 결국 계산이 불가능하다는 의미이므로 -1 로 처리하면 됩니다.

 

또한, ret에서 ret에 누적값을 더하는것이 아닌, 아래처럼 값으로 최소값으로 갱신시키는 이유는 무엇일까요?

ret1 = Math.min(ret1, knapsack(coinIdx, amount - Coins[coinIdx]) + 1);

이유는 최소값을 계속해서 갱신하기 위해서입니다.

만약 ret1 += 로 처리했다면, 이전값이 현재값에 영향을 미치는데 그렇게 되면 최소 동전의 개수를 못구하게 됩니다. 즉, 모든 동전의 개수로 amount를 만들 수 있는 모든 경우의 수를 구하게 되겠지요.

코드

class Solution {
    int[] Coins;
    int[][] cache;
    int Amount;
    final int MAXAMOUNT = 10001;
    public int coinChange(int[] coins, int amount) {
        Coins = coins; Amount = amount;
        cache = new int[coins.length][MAXAMOUNT + 1];
        for(int i=0; i<coins.length; i++){
            Arrays.fill(cache[i], -1);
        }
        int answer = knapsack(0, amount);
        return answer > amount ? -1 : answer;
    }

    int knapsack(int coinIdx, int amount){
        if(amount == 0){
            return 0;
        }
        if(cache[coinIdx][amount] != -1) return cache[coinIdx][amount];
        int ret1 = MAXAMOUNT;
        if(coinIdx < Coins.length && amount - Coins[coinIdx] >= 0)
            ret1 = Math.min(ret1, knapsack(coinIdx, amount - Coins[coinIdx]) + 1);

        if(coinIdx + 1 < Coins.length)
            ret1 = Math.min(ret1, knapsack(coinIdx + 1, amount));

        return cache[coinIdx][amount] = ret1;
    }
}