Min Coin改变自上而下的方法

Question

我试图解决Leetcode上的最小硬币更换问题，但只通过了一些测试。我使用Java语言，我的方法是动态自上而下的方法。我知道这个问题可能与某些情况有关，即金额无法计算到给定的硬币零钱，但不知道如何解决。谢谢，伙计们！

这就是的问题

You are given an integer array of coins representing coins of different denominations and an integer amount representing a total amount of money.
Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.
You may assume that you have an infinite number of each kind of coin.
Example 1:
Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

这是我的解决方案

public int coinChange(int[] coins, int amount) {
if (amount == 0)
return 0;
int [] dp = new int[amount + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
int start = 0;
int res = helper(coins, dp, amount, start);
if(res == Integer.MAX_VALUE)
return -1;
return res;
}

public int helper(int[]coins, int [] dp, int amount, int start ){
if(amount == 0)
return 0;
if(dp[amount] != Integer.MAX_VALUE)
return dp[amount];
for (int i = start; i < coins.length; ++i){
if(coins[i] <= amount){
int coinToTakeAtThatAmount = helper(coins, dp, amount - coins[i], i) + 1;
dp[amount] = Math.min(dp[amount],  coinToTakeAtThatAmount );
}          
}
return dp[amount];
}

Answer 1

有几个问题：

• Integer.MAX_VALUE + 1为负值。由于helper可以返回Integer.MAX_VALUE，因此不应向其添加1。一种解决方案是评估1 + Math.min(dp[amount] - 1, helper(.....))。

• dp数组有时会获得当start大于0时发现的值。这意味着当你可用的硬币较少时，它代表了一个解决方案。然而，当退出几个递归级别时，可能会有一个新的调用，其中start更少，从而允许更多硬币，但当有更多硬币可用时，if(dp[amount] != Integer.MAX_VALUE)将选择一个可能不是最佳的解决方案。

解决第二点的一个想法是为dp保留一个二维数组，其中start的值也用于一个维度，但这不够有效。

一个更好的想法是为所有基于一个硬币的金额填充1-Ddp数组，然后通过使用第二个硬币来找到改进，。。。等等。这实际上可以在没有递归的情况下通过迭代来完成。

因此，一个可行的解决方案是：

public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, Integer.MAX_VALUE);
// Base case: the number of coins needed for getting 0 is 0.
dp[0] = 0;
// Consider one coin at a time: 
for (int coin : coins) {
// Find improvements for each individual amount, making use of this coin
for (int target = coin; target <= amount; target++) {
// See if using this coin is an improvement. Avoid adding to MAX_VALUE
dp[target] = 1 + Math.min(dp[target] - 1, dp[target - coin]);
}
}
return dp[amount] != Integer.MAX_VALUE ? dp[amount] : -1;
}