錢幣更改動態編程

Question

問題： 我無法找到達到特定金額所需的最少金額。我很確定這是最簡單的遞歸方式，並使用動態編程方法，我基本上應該得到Math.min（「takeACoin」，「leaveACoin」）; 不幸的是，我的代碼並沒有終止，雖然我確實有if語句，在符合總和條件下終止，硬幣數組耗盡，或者總和結束。請看下面的代碼，讓我知道我做錯了什麼，特別是爲什麼我的代碼繼續執行，直到它收到一個stackoverflow錯誤，雖然我有適當的終止條件。

CODE：

private static final int S = 3; 
public static int arr[] = {1,2}; 
public static void main(String[] args) { 
    Interview i = new Interview(); 
    i.sumCoins(arr, 0); 
} 
public int sumCoins(int[] ar, int sum) { 
    //if the sum is met, dont add any coins, just return 0 
    if(sum == S){ 
     return 0; 
    } 
    //if the sum is greater, then return max value as it is impossible to get less sum 
    if(sum > S){ 
     return Integer.MAX_VALUE; 
    } 
    //if the array is out of coins return max value 
    if(ar.length == 0){ 
     return Integer.MAX_VALUE; 
    } 
    //if the sum is less than S and there is still more coins to use, keep checking 
    //add the first coin 
    int tmpSum = sum + ar[0]; 
    //delete the first coin from the list 
    int[] tmp = Arrays.copyOfRange(ar, 1, ar.length); 
    //add one coin to the solution 
    int one = 1+sumCoins(tmp, tmpSum); 
    //don't add one coin to the solution 
    int two = sumCoins(ar,sum); 

    //see which is more minimized 
    return Math.min(one,two); 
} 

請求堆棧跟蹤：在螺紋
異常 「主」 java.lang.StackOverflowError的

在java.lang.Math.min（Math.java:879）
在java.util.Arrays.copyOfRange（Arrays.java:2623）
在Interview.sumCoins（Interview.java:28）
在Interview.sumCoins（Interview.java:32）
at Interview.sumCoins（Interview.java:32）

Answer 1

這個問題的答案是關於我如何實現我的動態編程。在您離開硬幣的情況下，我正在使用原始數組。這是不正確的。詳細說明如下： 如果您拿出硬幣：擺脫陣列的第一個（硬幣）索引，添加總和，爲硬幣數量加+1。 如果你不把硬幣：擺脫硬幣的第一個（硬幣）索引，因爲你離開硬幣不被考慮。

在我的解決方案中，我收到了一個stackoverflow，因爲我正在經歷「離開硬幣」場景無限次，因爲數組永遠不會減少，我實際上並沒有「離開硬幣」。 正確的代碼在這裏：

private static final int S = 5; 
public static int arr[] = {1,1,1,1,1}; 
public static void main(String[] args) { 
    Interview i = new Interview(); 
    System.out.println(i.sumCoins(arr, 0)); 
} 
public int sumCoins(int[] ar, int sum) { 
    //if the sum is met, dont add any coins, just return 0 
    if(sum == S){ 
     return 0; 
    } 
    //if the sum is greater, then return global array (not local) 
    //length +1 as it's impossible to get more coins than indices 
    if(sum > S){ 
     return arr.length+1; 
    } 
    //if the array is out of coins return max value 
    if(ar.length == 0){ 
     return arr.length+1; 
    } 
    //if the sum is less than S and there is still more coins to use, keep checking 
    //add the first coin 
    int tmpSum = sum + ar[0]; 
    //delete the first coin from the list 
    int[] tmp = Arrays.copyOfRange(ar, 1, ar.length); 
    //add one coin to the solution 
    int one = 1+sumCoins(tmp, tmpSum); 
    //don't add one coin to the solution 
    int two = sumCoins(tmp,sum); 

    //see which is more minimized 
    return Math.min(one,two); 

}