时间戳

首页 > 解决方案 > 具有一维数组的最小硬币变化自上而下 DP

algorithm - 具有一维数组的最小硬币变化自上而下 DP

问题描述

这是来自 Leetcode 的硬币找零问题，对于给定的面额，你有无限的硬币，你必须找到满足给定总和所需的最少硬币。我尝试使用具有自上而下方法的一维缓存阵列来解决这个问题。基本测试用例通过了，但对于一些较大的总和和面额值则失败了。我的假设是我在遍历数组时做错了，可能会丢失一些子问题的计算，但无法找到解决问题的问题。

问题陈述：

给你一个整数数组coins，表示不同面额的硬币，一个整数表示总金额。

返回您需要的最少数量的硬币来弥补该金额。如果该金额不能由任何硬币组合弥补，则返回-1。
您可以假设您拥有无限数量的每种硬币。

输入：硬币 = [1,2,5]，金额 = 11

输出：3

解释：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;
    }

标签： algorithmdynamic-programming

解决方案

在现有值的情况下，您似乎不更新 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];
}

推荐阅读