时间戳

首页 > 解决方案 > Min Coin Change 自上而下的方法

algorithm - Min Coin Change 自上而下的方法

问题描述

我试图在 Leetcode 上解决最少的硬币变化问题，但只通过了一些测试。我使用 Java 语言，我的方法是动态自上而下的方法。我知道问题可能与某些情况有关，即无法根据给定的硬币变化计算金额，但不知道如何解决。多谢你们！

这就是问题

You are given an integer array of coins representing coins of different denominations and an integer amount representing a total amount of money.

Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Example 1:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

这是我的解决方案

    public int coinChange(int[] coins, int amount) {
        if (amount == 0)
            return 0;
        int [] dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        int start = 0;
        int res = helper(coins, dp, amount, start);
        if(res == Integer.MAX_VALUE)
            return -1;
        return res;
    }
    
    public int helper(int[]coins, int [] dp, int amount, int start ){
        if(amount == 0)
            return 0;
        if(dp[amount] != Integer.MAX_VALUE)
            return dp[amount];
        for (int i = start; i < coins.length; ++i){
            if(coins[i] <= amount){
                int coinToTakeAtThatAmount = helper(coins, dp, amount - coins[i], i) + 1;
                dp[amount] = Math.min(dp[amount],  coinToTakeAtThatAmount );
            }          
        }

        return dp[amount];
    }

标签： algorithmdynamic-programming

解决方案

有几个问题：

  • Integer.MAX_VALUE + 1是负值。正如helper可以返回的那样Integer.MAX_VALUE，您不应向其添加 1。一种解决方案是评估1 + Math.min(dp[amount] - 1, helper(.....)).

  • 该数组有时会获得大于 0dp时发现的值。这意味着当您可用的硬币较少时，它代表一种解决方案。start然而，当退出几个递归级别时，可能会有一个新的调用start较少，因此允许更多的硬币，但是if(dp[amount] != Integer.MAX_VALUE)当你有更多的硬币可用时，它会选择一个可能不是最佳的解决方案。

解决第二点的一个想法可能是为 维护一个二维数组dp，其中的值start也用于一个维度，但这不够有效。

dp一个更好的想法是仅基于一枚硬币填充所有金额的一维数组，然后通过使用第二枚硬币等来寻找改进。这实际上可以通过没有递归的迭代来完成。

所以一个可行的解决方案是：

public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    // Base case: the number of coins needed for getting 0 is 0.
    dp[0] = 0;
    // Consider one coin at a time: 
    for (int coin : coins) {
        // Find improvements for each individual amount, making use of this coin
        for (int target = coin; target <= amount; target++) {
            // See if using this coin is an improvement. Avoid adding to MAX_VALUE
            dp[target] = 1 + Math.min(dp[target] - 1, dp[target - coin]);
        }
    }
    return dp[amount] != Integer.MAX_VALUE ? dp[amount] : -1;
}

推荐阅读