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

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

 

처음에. 뭔가 큰수의 동전부터 갯수를 잡아나가야하는 줄 방향을 잘못잡았는데
생각해보니 나누어떨어지도록 해야해서. 작은 수부터 차차 구해서 피보나치 처럼 중복 연산 없게 해야했다.

 

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;
    }
}