硬币变化动态编程

Question

问题：我很难找到达到特定金额所需的最低硬币数量。我很确定这是最简单的递归方式，使用动态编程方法，我基本上应该得到Math.min（“获取ACoin”、“离开ACoin”）；不幸的是，我的代码不会终止，尽管我确实有在满足总和的条件下终止的if语句，硬币数组耗尽，或者如果总和结束。请查看下面的代码，让我知道我做错了什么，特别是为什么我的代码继续执行，直到它收到一个stackoverflow错误，尽管我有适当的终止条件。

代码：

    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);
}

请求的堆栈跟踪：
异常在线程"main"java.lang.StackOverflow错误

在java.lang.Math.min（Math.java:879）
在java.util.rrays.copyOfRange（rrays.java:2623）
在我nterview.sum硬币（我nterview.java:28）
在我nterview.sum硬币（我nterview.java:32）
在我nterview.sum硬币（我nterview.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);

}