我正在尝试寻找 coin change problem 的所有可能的解决方案.
示例:我有硬币 1 和 2,我想兑换 6。
正确解: [1,1,1,1,1,1], [2,1,1,1,1,0], [2,2,1,1, 0,0], ...
我的代码: [1,1,1,1,1,1], [1,1,1,1,0,0], [1,1,0,0, 0,0], ...
最后一行还删除了我的参数“coinsSoFar”,我不明白为什么。当我调试时,它将 temp 设置为 [0,0,0,0,0,0] 并且 coinSoFar 设置为 [0,0,0,0,0,0],它应该保持在 [2,0,0,0, 0,0]。
非常感谢您的帮助。 (clearArray:所有数字设置为0;addToArray:用数字替换前0)
public static void makeChange(int amount, int startCoinIndex, int[] coinsSoFar) {
if (amount == 0) {
System.out.println(Arrays.toString(coinsSoFar));
}
if (startCoinIndex == coinSet.length || amount < 0) {return;}
for (int i = 0; i * coinSet[startCoinIndex] <= amount; i++) {
int[] temp = coinsSoFar;
for (int j = 0; j < i; j++) {
addToArray(temp, coinSet[startCoinIndex]);
}
makeChange(amount - i * coinSet[startCoinIndex], startCoinIndex+1, temp);
clearArray(temp); // this line also clears coinsSoFar. Why?
}
}
最佳答案
当你这样做
int[] temp = coinsSoFar;
您正在设置 temp 以引用与 coinsSoFar
相同的数组。因此,您对 temp
所做的任何操作现在都会影响 coinsSoFar
。
如果您想让 temp
引用 coinsSoFar
的副本,请执行以下操作:
int[] temp = Arrays.copyOf(coinsSoFar, coinsSoFar.length);
// OR, if you prefer
int[] temp = new int[coinsSoFar.length];
System.arraycopy(coinsSoFar, 0, temp, 0, coinsSoFar.length);
关于java - 硬币找零 - 所有解决方案递归 - Java,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44043531/