最小硬币变化自上而下DP与1D阵列

Question

这是Leetcode的硬币兑换问题，在这里，给定面额的硬币是无限的，你必须找到满足给定金额所需的最小硬币。我尝试使用自顶向下的1D缓存阵列解决这个问题。基本测试用例通过了，但对于一些较大的总和和面额值，它失败了。我的假设是，我在遍历数组时做错了什么，可能遗漏了一些子问题的计算，但无法找到解决问题的方法。

问题陈述：

You are given an integer array 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.

Input: coins = [1,2,5], amount = 11

Output: 3

Explanation: 11 = 5 + 5 + 1

我的解决方案：

/* Test case, it's failing for: 
Input: coins: [186,419,83,408] 
sum = 6249 
Output: 26 
Expected: 20 
*/
------------------------------------------------------------------------

    int fncUtil(int dp[], int a[], int sum, int n, int curCoins) {


        if(sum == 0) {
            return curCoins;
        }

        if(n < 0 || sum < 1) {
            return Integer.MAX_VALUE;
        }

        if(dp[sum] != Integer.MAX_VALUE) {
            return dp[sum];
        }

        dp[sum] = Math.min(fncUtil(dp, a, sum - a[n], n, curCoins+1),
                    fncUtil(dp, a, sum, n-1, curCoins));

        return dp[sum];

    }
    public int coinChange(int[] a, int sum) {
        Arrays.sort(a);
        int n = a.length;
        // minCoins = Integer.MAX_VALUE;
        int dp[] = new int[sum+1];
        for(int i = 0; i <= sum; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        dp[0] = 0;
        int minCoins = fncUtil(dp, a, sum, n-1, 0);
        if(minCoins == Integer.MAX_VALUE) return -1;
        return minCoins;
    }

Answer 1

似乎在存在值的情况下不更新dp数组

if(dp[sum] != Integer.MAX_VALUE) {
         return dp[sum];
  }

也许您需要从三个变体中选择最好的

  dp[sum] = Math.min(dp[sum], 
         Math.min(fncUtil(dp, a, sum - a[n], n, curCoins+1), fncUtil(dp, a, sum, n-1, curCoins)));

但是我们可以使用自下而上的顺序（未检查）来解决这个问题，而无需递归

public int coinChange(int[] a, int sum) {
    int n = a.length;
    int dp[] = new int[sum+1];
    for(int i = 0; i <= sum; i++) {
        dp[i] = Integer.MAX_VALUE - 1;
    }
    dp[0] = 0;
    for(int i = 0; i < n; i++) {
        for (int k = a[i]; k <= sum; k++) {
               dp[k] = Math.min(dp[k], dp[k-a[i]] + 1);
        } 
    }
    return dp[sum];
}