硬币变化动态规划-Java 学习之路

问题：我很难找到达到特定金额所需的最低金额 . 我很确定这是最简单的递归和使用动态编程方法，我应该基本上得到Math.min（“takeACoin”，“leaveACoin”）;不幸的是，我的代码没有终止，虽然我确实有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.StackOverflowError中的异常

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

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

}

回复于 2024-04-20T07:14:34+08:00

硬币变化动态规划

1 回答

相关问题