Coin Change - Java 未能通过示例 3

Question

问题：给你不同面额的硬币和总金额。编写一个函数来计算您需要最少的硬币数量来弥补该金额。如果那个数额的钱不能由硬币的任意组合组成，return -1.

示例 1：

输入：硬币 = [1, 2, 5], 数量 = 11 输出：3 解释：11 = 5 + 5 + 1

示例 2：

输入：硬币=2，数量=3 输出：-1

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

我的代码：

public int coinChange(int[] coins, int amount) {
    Arrays.sort(coins);
    int new_amount=amount;
    int count_coin=0;
    int q=0,r=0,a=0;
    int k=coins.length-1;


    while(amount>0 && k>=0) {

            q = new_amount / coins[k];
            count_coin = count_coin + q;
            r = new_amount % coins[k];
            new_amount=r;
            a+=q*coins[k];
            k--;



    }


    if(a==amount){
        return count_coin;
    }
    else{
        return -1;
    } }

对于给定的两个示例，我的代码运行良好。在使用这个示例之后，我进行了另一个测试用例。

示例3:Input：硬币= [186,419,83,408]，金额= 6249 输出：20 我的输出：-1

我没看懂这个例子。如果有人对这个例子有任何想法，或者除了我的算法之外还有其他更好的算法，请与我分享。

我看到了Coin Change (Dynamic Programming)link。但是看不懂。

我也研究过为什么贪心找零算法对某些币种不适用？但无法理解它试图做什么 say.So 我提出了这个问题。

提前致谢。

Answer 1

您的代码使用的 greedy 方法不适用于任意硬币面额（例如，设置 3,3,4 无法产生答案 6）

改为使用动态规划方法(example)

例如，制作长度为 amount+1 的数组 A，用零填充，制作 A[0] = 1 并从第 n 个条目向下遍历每个硬币面值的数组，选择每个单元格的最佳结果。

伪代码：

 for (j=0; j < coins.length; j++) {
     c = coins[j];
     for (i=amount; i >= c; i--){
          if (A[i - c] > 0)
              A[i] = Min(A[i], A[i - c] + 1);
     }
 }
 result = A[amount] - 1;

Coin Change - Java 未能通过示例 3

Coin Change - Java Fail to pass example 3

java

algorithm

dynamic-programming

brute-force

while-loop