LeetCode 322. 零钱兑换 多种思路
程序员文章站
2022-04-04 09:03:02
...
自下而上动态规划
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
// 初始化数组
for(int i = 1;i< dp.length;i++){
dp[i] = amount + 1;
}
for(int i = 1;i < dp.length;i++){
for(int j = 0;j < coins.length; j++){
if(i >= coins[j])
dp[i] = Math.min(dp[i - coins[j]] + 1,dp[i]);
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
自上而下动态规划递归
public int coinChange(int[] coins, int amount) {
if (amount < 1) {
return 0;
}
return coinChange(coins, amount, new int[amount]);
}
private int coinChange(int[] coins, int amount, int[] dp) {
if (amount < 0) {
return -1;
}
if (amount == 0) {
return 0;
}
if (dp[amount - 1] != 0) {
return dp[amount - 1];
}
int min = Integer.MAX_VALUE;
for (int coin : coins) {
int res = coinChange(coins, amount - coin, dp);
if (res >= 0 && res < min) {
min = 1 + res;
}
}
dp[amount - 1] = (min == Integer.MAX_VALUE) ? -1 : min;
return dp[amount - 1];
}
贪心法+dfs+剪枝
int ans = Integer.MAX_VALUE;
public int coinChange(int[] coins, int amount) {
if (amount == 0) return 0;
//排序,从大到小排序
int index,max,temp;
for (int i = 0; i < coins.length; i++) {
index = i;
max = Integer.MIN_VALUE;
for (int j = i; j < coins.length; j++) {
if (coins[j] > max){
max = coins[j];
index = j;
}
}
temp = coins[i];
coins[i] = max;
coins[index] = temp;
}
coinChange(coins, amount, 0, 0);
return ans == Integer.MAX_VALUE ? -1 : ans;
}
private void coinChange(int[] coins, int amount, int index, int count) {
if (amount == 0) {
ans = Math.min(ans, count);
return;
}
if (index == coins.length) return;
for (int k = amount / coins[index]; k >= 0 && k + count < ans; k--) {
coinChange(coins, amount - k * coins[index], index + 1, count + k);
}
}
上一篇: 已知三点算同距的点
下一篇: Leetcode2 两数相加