Leetcode 322) Coin Change

31 Jul 2021 in Algorithms

• 그림으로 한 번 그려봐도 좋을 듯?

내 답안

• recursive하게 푸는게 아니라, 만약 amount가 59이라면, 60짜리 크기 array를 만들어서 처음 숫자 1부터 차례대로 계산한다.

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] records = new int[amount+1];        
        records[0]=0;

        Arrays.sort(coins);

        for(int i=1;i<records.length;i++){
            int min = Integer.MAX_VALUE;
            for(int j=0;j<coins.length;j++){
                int remain = i-coins[j];
                if(remain>=0 && records[remain]!=-1){
                    min=Math.min(min,1+records[remain]);
                }
            }

            if(min==Integer.MAX_VALUE){
                records[i]=-1;
            }else{
                records[i]=min;
            }

        }
        return records[amount];

    }
}

다른 답안

class Solution {
    public int coinChange(int[] coins, int amount) {
        if(amount == 0)return 0;
        if(coins.length == 1 && amount < coins[0])return -1;

        int[] dp = new int[amount+1]; 
        Arrays.fill(dp,amount+1);  //coin value cannot be less than 1, so answer cannot be bigger than amount,so no need to use MAX_INT as initial value
        dp[0] = 0;

        for(int num:coins){
            for(int i = num;i<=amount;i++){
                dp[i] = Math.min(dp[i-num]+1,dp[i]);   //we add value on dp array , this is another reason why array cannot initialiaze as MAX_INT , cause it will overflow when value increase
            }
        }

        //if dp[amount] bigger than amount that means we cannot get valid answer,so return -1
        return dp[amount] > amount? -1 : dp[amount];

    }
}