动态编程-做出改变

Question

我在弄清楚动态硬币更换问题的最后代码方面遇到麻烦。我已包含以下代码。

我不知道最后一个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];
}

Answer 1

您不需要切换到贪婪算法来解决硬币兑换问题，您可以使用动态编程算法来解决它。例如，像这样：

public int minChange(int[] denom, int targetAmount) {

    int actualAmount;
    int m = denom.length+1;
    int n = targetAmount + 1;
    int inf = Integer.MAX_VALUE-1;

    int[][] table = new int[m][n];
    for (int j = 1; j < n; j++)
        table[0][j] = inf;

    for (int denomPosition = 1; denomPosition < m; denomPosition++) {
        for (int currentAmount = 1; currentAmount < n; currentAmount++) {
            if (currentAmount - denom[denomPosition-1] >= 0)
                actualAmount = table[denomPosition][currentAmount - denom[denomPosition-1]];
            else
                actualAmount = inf;
            table[denomPosition][currentAmount] = Math.min(table[denomPosition-1][currentAmount], 1 + actualAmount);
        }
    }

    return table[m-1][n-1];

}