题目
image.png
题解
题解1
class Solution {
public int coinChange(int[] coins, int amount) {
if (dfs(coins, amount) > amount) {
return -1;
}
return dfs(coins, amount);
}
private int dfs(int[] coins, int amount) { // 组成当前amount的最少硬币个数
if (amount < 0) {
return amount + 100;
}
if (amount == 0) {
return 0;
}
int res = Integer.MAX_VALUE;
for (int i = 0; i < coins.length; i++) {
int tmp = dfs(coins, amount-coins[i]) + 1;
res = Math.min(res, tmp);
}
return res;
}
}
image.png
怎么处理-1的问题，即没有解的情况，通过return设置特殊解
题解2
class Solution {
public int coinChange(int[] coins, int amount) {
if (dfs(coins, amount) == Integer.MAX_VALUE) { // ??
return -1;
}
return dfs(coins, amount);
}
private int dfs(int[] coins, int amount) { // 组成当前amount的最少硬币个数
if (amount < 0) {
return -1;
}
if (amount == 0) {
return 0;
}
int res = Integer.MAX_VALUE;
for (int i = 0; i < coins.length; i++) {
int tmp = dfs(coins, amount-coins[i]);
if (tmp == -1) { // 无解
continue;
}
res = Math.min(res, tmp+1);
}
return res;
}
}
结果
image.png
题解3
暴力解法的正确写法
注意：在return之前判断是不是正无穷，与题解2的区别
class Solution {
public int coinChange(int[] coins, int amount) {
return dfs(coins, amount);
}
private int dfs(int[] coins, int amount) {
if (amount == 0) {
return 0;
}
if (amount < 0) {
return -1;
}
int res = Integer.MAX_VALUE;
for (int i = 0; i < coins.length; i++) {
// res = Math.min(res, dfs(coins, amount-coins[i])+1);
int tmp = dfs(coins, amount-coins[i]);
if (tmp == -1) {
continue;
}
res = Math.min(res, dfs(coins, amount-coins[i])+1);
}
if (res == Integer.MAX_VALUE) {
return -1;
}
return res;
}
}
题解4
对题解3优化
class Solution {
public int[] dp;
public int coinChange(int[] coins, int amount) {
dp = new int[amount + 1];
return dfs(coins, amount);
}
private int dfs(int[] coins, int amount) {
if (amount == 0) {
return 0;
}
if (amount < 0) {
return -1;
}
if (dp[amount] != 0) {
return dp[amount];
}
int res = Integer.MAX_VALUE;
for (int i = 0; i < coins.length; i++) {
// res = Math.min(res, dfs(coins, amount-coins[i])+1);
int tmp = dfs(coins, amount-coins[i]);
if (tmp == -1) {
continue;
}
res = Math.min(res, dfs(coins, amount-coins[i])+1);
}
// dp[amount] = res;
if (res == Integer.MAX_VALUE) {
dp[amount] = -1;
return -1;
}
dp[amount] = res;
return res;
}
}
题解5
对题解4的dp优化
class Solution {
public int[] dp;
public int coinChange(int[] coins, int amount) {
dp = new int[amount + 1];
for (int i = 1; i <= amount; i++) {
if (dp[i] != 0) {
continue;
}
int res = Integer.MAX_VALUE;
for (int t = 0; t < coins.length; t++) {
if (i < coins[t]) {
continue;
}
if (dp[i-coins[t]] == -1) { // 子问题无解
continue;
}
res = Math.min(res, dp[i-coins[t]]+1);
}
if (res == Integer.MAX_VALUE) { //
dp[i] = -1;
} else {
dp[i] = res;
}
}
return dp[amount];
}
}
参考题解
class Solution {
public int coinChange(int[] coins, int amount) {
if (amount<=0) return 0;
int[] dp = new int[amount+1];
for (int i=0; i<=amount; i++)
Arrays.fill(dp, amount+1);
dp[0] = 0;
for (int i=1; i<=amount; i++)
for (int coin:coins){
dp[i] = Math.min(dp[i], (i-coin>=0?dp[i-coin]+1:amount+1)); // 求min和max是不同的
}
return dp[amount]>amount?-1:dp[amount];
}
}
