[Leetcode] 322. Coin Change (JAVA)

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

Example 4:

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

Example 5:

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

Constraints:

1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104

My Code

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        for(int i=1 ; i<=amount ; i++) {
            dp[i] = amount+1;
            for(int coin : coins) {
                if(i-coin>=0) {
                    dp[i] = Math.min(dp[i],dp[i-coin]+1);
                }
            }
        }
        return dp[amount]>amount?-1:dp[amount];
    }
}

Comment

처음 DP 공부했던 기억을 떠올리게한 문제
딱히 명쾌한 해설이 없어서 인도 개발자분 설명을 듣고
감탄했던 기억이 남.
잘하지도 못한 영어가 그때는 그렇게 이해가 잘되었었음.