java - DP-Coin 找零结果为零

Question

所以这是我的代码，我试图找出从无限供应的硬币中组成我的目标数量的最小硬币数量。我的问题是我没有得到所需的硬币数量，而是得到了 0。那么我该如何解决这个问题呢？如果我不清楚的话，很抱歉。我的英语不太好:(。这是我的代码:

import java.util.*;
public class CoinChangeDP{
   public static int[] c = {1,2,2,5,5,5,10};
   public static int amount = 15;
   public static int[][] dp = new int[c.length+1][amount+1];
   public static void main(String[] args){
      System.out.println("Minimum number of coin required: "+CoinChange(0, amount));
  }
  public static int CoinChange(int index, int amount){
     int n = c.length;
     if(index>=n){
        if(amount==0)
           return 0;
        else
           return Integer.MAX_VALUE;
     }
     if(dp[index][amount]!=-1){
         return dp[index][amount];
     }
     int ret1, ret2;
     if(amount>=c[index]){
         ret1 = 1+CoinChange(index, amount-c[index]);
     }else{
         ret1 = Integer.MAX_VALUE;
     }
     ret2 = CoinChange(index, amount);
     dp[index][amount] = Math.min(ret1, ret2);
     return dp[index][amount];
 } 

}

Answer 1

dp 数组用零初始化，因此当您第一次调用时检查:

if(dp[index][amount]!=-1){
         return dp[index][amount];
}

它将返回0。在调用 coinChange() 函数之前用 -1 填充您的 dp 数组:

for (int[] d : dp) {
    Arrays.fill(d, -1);
}
System.out.println("Minimum number of coin required: "+CoinChange(0, amount));

编辑:这是您的函数的固定版本(按照注释):

 public static int CoinChange(int index, int amount){
     int n = c.length;
     // check if at any point we reached 0 amount (got a solution)
     if (amount == 0) {
         return 0;
     }
     // if we reached the end of the array and we still have amount > 0
     if (index == n){
         return Integer.MAX_VALUE;
     }
     // if we already processed the value for this index/amount
     if (dp[index][amount] != -1){
         return dp[index][amount];
     }
     int ret1, ret2;
     if(amount >= c[index]){
         // take this coin and stay on same index
         ret1 = 1+CoinChange(index, amount-c[index]);
     }else{
         ret1 = Integer.MAX_VALUE;
     }
     // do not take this coin and go to next index
     ret2 = CoinChange(index+1, amount);
     dp[index][amount] = Math.min(ret1, ret2);
     return dp[index][amount];
 } 

关于您关于无限供应的问题，这里各州要么拿走代币并保留在同一索引上(在下次调用时拿走或离开)，要么留下它并转到下一个索引。第一个函数调用将尝试取走或留下硬币，只要它<=金额，因此这将涵盖所有可能的情况。