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?