java - 硬币找零算法总是返回一个

Question

/**
 * 
 * @param d
 *            currency divisions
 * @param p
 *            target
 * @return number of coins
 */
public static int change(int[] d, int p) {
    int[] tempArray = new int[p*2]; // tempArray to store set
                                                    // of coins forming
                                                    // answer
    for (int i = 1; i <= p; i++) { // cycling up to the wanted value
        int min = Integer.MAX_VALUE; //assigning current minimum number of coints
        for (int value : d) {//cycling through possible values
            if (value <= i) {
                if (1 + tempArray[i - value] < min) { //if current value is less than min
                    min = 1 + tempArray[1 - value];//assign it
                }
            }
        }
        tempArray[i] = min; //assign min value to array of coins
    }
    return tempArray[p];
}

谁能帮我看看为什么这不起作用？该方法旨在获得代表硬币的值的输入，它具有无限数量的这些硬币来形成整数 p，该方法是返回用于到达 p 的最小硬币数量。

Answer 1

tempArray 在所有索引上初始化为 0。使用 tempArray[1-value] 基本上给你 0。所以，从 1 到 p 的所有索引都有值 1 + tempArray[1-value] 这是 1。此外，tempArray[1-value] 是一个负索引。我认为您的意思是 tempArray[i-value]