Coin Change

์ž๋ฃŒ๊ตฌ์กฐ : 1์ฐจ์› DP๋ฐฐ์—ด.

  • ๋ฐฐ์—ด์˜ ํฌ๊ธฐ = amount+1.

  • index = amount๋ฅผ ์˜๋ฏธ.

  • DP[index] = ํ•ด๋‹น index amount๋ฅผ ๋งŒ๋“ค๊ธฐ ์œ„ํ•œ ์ฝ”์ธ ๊ฐฏ์ˆ˜.

์•Œ๊ณ ๋ฆฌ์ฆ˜ - DP ์•Œ๊ณ ๋ฆฌ์ฆ˜ 1. sub-problem์—์„œ๋ถ€ํ„ฐ ์‹œ์ž‘ํ•ด์„œ ํ•ด๋ฅผ ๊ตฌํ•œ๋‹ค!! - dp[0]๋ถ€ํ„ฐ ์‹œ์ž‘ํ•œ๋‹ค. 2. sub-problem์˜ ํ•ด๋ฅผ ์ฐจ๊ทผ์ฐจ๊ทผ ๊ตฌํ•ด์„œ ์ตœ์ข…์ ์ธ ํ•ด๋ฅผ ๊ตฌํ•œ๋‹ค! - Coin Change

์•Œ๊ณ ๋ฆฌ์ฆ˜->Java๋กœ ๊ตฌํ˜„ 1)2์ฐจ์› ๋ฐฐ์—ด DP

class Solution {
    public int coinChange(int[] coins, int amount) {
        int m = amount;
        int n = coins.length;
        
        //0.data structure
        int[][] dp = new int[n+1][m+1];
        //1.
        for(int i=0; i<= n;i++) {
            for(int j=0; j <= m;j++) {
                if(j == 0) {
                    dp[i][j] = 0;
                } else if(i == 0) {
                    dp[i][j] = 100000;
                }
                /*if(i == 0 || j == 0) {
                    dp[i][j] = 0;//boundary case
                }*/ else if(coins[i-1] > j) {
                    dp[i][j] = dp[i-1][j];
                } else {//actual algorithm
                    dp[i][j] = Math.min(dp[i-1][j],1+dp[i][j-coins[i-1]]);
                }
            }
        }
        return dp[n][m] > 1e4 ? -1 : dp[n][m];
    }
}

2) 1์ฐจ์› ๋ฐฐ์—ด DP

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

Last updated

Was this helpful?