322. Coin Change

문제

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

풀이

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

• 해당 amount까지의 최적해를 지속적으로 구해감
  • 현재 coin들로 만들 수 없다면 Integer.MAX_VALUE
  • dp[amount]가 Integer.MAX_VALUE라면 만들 수 없는 amount이므로 -1 return