Leet code (Medium) : 322. Coin Change - JAVA

dp의 가장 정석적인 문제라고도 할 수 있는 동전 문제다. 

 

처음에. 뭔가 큰수의 동전부터 갯수를 잡아나가야하는 줄 방향을 잘못잡았는데

꼭 구성 동전들로 뺐을 때, 0이 되어야 하는 건 아니고, 

dp로 금액인 amount를 구성하능한 그러니까 amount 보다 합이 작거나 같은 최소 동전의 수를 구하면 된다.

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] ans = new int[amount+1];
        Arrays.fill(ans, amount+1);
        ans[0] = 0;
        for(int i = 1; i <= amount; i++){
            for(int j = 0; j < coins.length; j++){
                if(i - coins[j] >= 0){
                    ans[i] = Math.min(ans[i], 1 + ans[i-coins[j]]);
                }
            }
        }

        return ans[amount] != amount + 1 ? ans[amount] : -1;
    }
}