我无法弄清楚动态硬币更换问题的最后一段代码。我已经包含了下面的代码。
我想不通最后一个else
。那时我应该只使用贪心算法,还是可以根据表中已有的值计算答案?我一直在努力理解这个问题,我想我已经很接近了。该方法通过创建一个表并使用存储在表中的结果来解决更大的问题而不使用递归来找到产生一定数量的零钱所需的最小硬币数量。
public static int minCoins(int[] denom, int targetAmount){
int denomPosition; // Position in denom[] where the first spot
// is the largest coin and includes every coin
// smaller.
int currentAmount; // The Amount of money that needs to be made
// remainingAmount <= initalAmount
int[][] table = new int[denom.length][targetAmount+1];
for(denomPosition = denom.length-1 ; denomPosition >= 0 ; denomPosition--) {
for(currentAmount = 0 ; currentAmount <= targetAmount ; currentAmount++){
if (denomPosition == denom.length-1){
table[denomPosition][currentAmount] =
currentAmount/denom[denomPosition];
}
else if (currentAmount<denom[denomPosition]){
table[denomPosition][currentAmount] =
table[denomPosition+1][currentAmount];
}
else{
table[denomPosition][currentAmount] =
table[denomPosition+1][currentAmount]-
table[denomPosition][denom[denomPosition]]-1;
}
}
}
return table[0][targetAmount];
}