參考資料：
1. 動(dòng)態(tài)規(guī)劃之背包問題系列
背包問題的定義參見參考資料1
跟背包問題不同的是匆骗，目標(biāo)是換的零錢的個(gè)數(shù)最少。
零錢個(gè)數(shù)不限誉简，所以是完全背包問題碉就。
因?yàn)橐婚_始沒有答案，所以初始化為INVALID闷串，背包問題一開始初始化為0铝噩，因?yàn)楸嘲裁炊疾谎b，0也算背包的收益窿克。
- 分析一迭代求法
private int INVALID = Integer.MAX_VALUE;
// 分析一 迭代求法
public int coinChange(int[] coins, int amount){
int[][] dp = new int[coins.length+1][amount+1];
for (int i = 0; i < dp.length; i++) {
Arrays.fill(dp[i], INVALID);
}
for (int i = 0; i < dp.length; i++) {
dp[i][0] = 0;
}
for (int i = 1; i <= coins.length; i++) {
for (int j = 1; j <= amount; j++) {
int use;
if(j >= coins[i-1]){
use = dp[i][j - coins[i-1]];
if(use != INVALID){
use += 1;
}
}else{
use = INVALID;
}
dp[i][j] = Math.min(dp[i-1][j], use);
}
}
return dp[coins.length][amount] == INVALID ? -1:dp[coins.length][amount];
}
- 分析一節(jié)省空間解法
private int INVALID = Integer.MAX_VALUE;
// 分析一 節(jié)省空間
public int coinChange(int[] coins, int amount){
int[] dp = new int[amount+1];
Arrays.fill(dp, INVALID);
dp[0] = 0;
for (int i = 1; i <= coins.length; i++) {
for (int j = 1; j <= amount; j++) {
int use;
if(j >= coins[i-1]){
use = dp[j - coins[i-1]];
if(use != INVALID){
use += 1;
}
}else{
use = INVALID;
}
dp[j] = Math.min(dp[j], use);
}
}
return dp[amount] == INVALID ? -1:dp[amount];
}
- 分析一遞歸解法
private int INVALID = Integer.MAX_VALUE;
public int coinChange(int[] coins, int amount){
if(amount==0)
return 0;
if(coins.length==0)
return -1;
int[][] dp = new int[coins.length][amount+1];
int result = coinChange(coins, amount, dp, coins.length-1);
return result == INVALID ? -1:result;
}
private int coinChange(int[] coins, int amount, int[][] dp, int indexOfLastCoin) {
if(dp[indexOfLastCoin][amount] != 0)
return dp[indexOfLastCoin][amount];
int use = INVALID;
int leftAmount = amount - coins[indexOfLastCoin];
if(leftAmount > 0){
use = coinChange(coins, leftAmount, dp, indexOfLastCoin);
if(use!=INVALID){
use += 1;
}
} else if(leftAmount == 0){
use = 1;
}
int notUsed = INVALID;
int indexOfLeftCoin = indexOfLastCoin - 1;
if(indexOfLeftCoin >= 0){
notUsed = coinChange(coins, amount, dp, indexOfLeftCoin);
}
dp[indexOfLastCoin][amount] = Math.min(use, notUsed);
// System.out.println("dp[" + indexOfLastCoin + "][" + amount + "]:"+dp[indexOfLastCoin][amount]);
return dp[indexOfLastCoin][amount];
}
- 分析二迭代求法
private int INVALID = Integer.MAX_VALUE;
// 分析二 根據(jù)amount限制對(duì)應(yīng)的硬幣個(gè)數(shù)骏庸，在01背包里面加上一層循環(huán)
public int coinChange(int[] coins, int amount){
int[][] dp = new int[coins.length+1][amount+1];
for (int i = 0; i < dp.length; i++) {
Arrays.fill(dp[i], INVALID);
}
for (int i = 0; i < dp.length; i++) {
dp[i][0] = 0;
}
for (int i = 1; i <= coins.length; i++) {
for (int j = 1; j <= amount; j++) {
int min = INVALID;
// 這里k必須從0開始，不一定要用到conis[i-1]年叮，可以不用具被；
for (int k = 0; k <= j/coins[i-1]; k++) {
int leftAmount = j-coins[i-1]*k;
if(leftAmount < 0 || dp[i-1][leftAmount]==INVALID)
continue;
min = Math.min(min, dp[i-1][leftAmount] + k);
}
dp[i][j] = min;
}
}
return dp[coins.length][amount] == INVALID ? -1:dp[coins.length][amount];
}
- 分析二節(jié)省空間版本
private int INVALID = Integer.MAX_VALUE;
// 分析二節(jié)省空間版本 根據(jù)amount限制對(duì)應(yīng)的硬幣個(gè)數(shù)，在01背包里面加上一層循環(huán)
public int coinChange(int[] coins, int amount){
int[] dp = new int[amount+1];
Arrays.fill(dp, INVALID);
dp[0] = 0;
for (int i = 1; i <= coins.length; i++) {
for (int j = amount; j >= 1; j--) {
int min = INVALID;
// 這里k必須從0開始只损，不一定要用到conis[i-1]一姿，可以不用；
for (int k = 0; k <= j/coins[i-1]; k++) {
int leftAmount = j-coins[i-1]*k;
if(leftAmount < 0 || dp[leftAmount]==INVALID)
continue;
min = Math.min(min, dp[leftAmount] + k);
}
dp[j] = min;
}
}
return dp[amount] == INVALID ? -1:dp[amount];
}
- 分析二遞歸求法（DFS剪枝版本跃惫，每個(gè)硬幣使用的次數(shù)是有上限的叮叹，超時(shí)！１妗）
private int INVALID = Integer.MAX_VALUE;
// 分析二遞歸版本 根據(jù)amount限制對(duì)應(yīng)的硬幣個(gè)數(shù)蛉顽，在01背包里面加上一層循環(huán)
public int coinChange(int[] coins, int amount){
int result = coinChange(coins, amount, 0, 0);
return result == INVALID?-1:result;
}
private int coinChange(int[] coins, int amount, int coinIndex, int coinUsed) {
if(amount==0)
return coinUsed;
if(coinIndex==coins.length)
return INVALID;
int min = INVALID;
for (int i = 0; i <= amount / coins[coinIndex]; i++) {
min = Math.min(min, coinChange(coins, amount - coins[coinIndex] * i, coinIndex + 1, coinUsed+i));
}
return min;
}
- 其他DFS剪枝版本
// DFS 剪枝
private int min = Integer.MAX_VALUE;
public int coinChange(int[] coins, int amount) {
if(amount==0)
return 0;
int[] sortedCoins = Arrays.stream(coins).boxed().sorted(Comparator.reverseOrder()).mapToInt(Integer::intValue).toArray();
coinChange(sortedCoins, 0, amount, 0);
return min==Integer.MAX_VALUE?-1:min;
}
private void coinChange(int[] coins, int start, int amount, int usedCoins) {
if(amount<0) {
return ;
}
if(amount==0) {
min = Math.min(usedCoins, min);
}
for (int i = start; i < coins.length; i++) {
// min 代表題目給的amount目前找到的最小的硬幣的個(gè)數(shù)
// min - usedCoins 代表還可以使用最多的個(gè)數(shù)
// coins[i]是最大的，所以coins[i]*(min - usedCoins)都湊不夠先较，不用試了携冤。
if(min!= Integer.MAX_VALUE && (coins[i]*(min - usedCoins))<amount)
return ;
coinChange(coins, i, amount-coins[i], usedCoins + 1);
}
}
- BFS
// BFS 從某個(gè)點(diǎn)是amount開始悼粮，coin是邊
public int coinChange(int[] coins, int amount) {
if (amount == 0)
return 0;
Deque<Integer> queue = new LinkedList<>();
Set<Integer> set = new HashSet<>();
queue.add(0);
set.add(0);
int numCoins = 0;
while(queue.size()!=0){
int size = queue.size();
numCoins += 1;
for (int i = 0; i < size; i++) {
int element = queue.removeFirst();
set.remove(element);
for (int coin : coins) {
int newElement = element + coin;
if(newElement==amount) {
return numCoins;
}else if(newElement < amount) {
if(!set.contains(newElement)) {
queue.addLast(newElement);
set.add(newElement);
}
}
}
}
}
return -1;
}
