Minimum Coin Change Top Down DP with 1D array

Question

This is coin change problem from Leetcode where you have infinite coins for given denominations and you have to find minimum coins required to meet the given sum. I tried solving this problem using 1D cache array with top-down approach. Basic test cases were passed but it failed for some larger values of the sum and denominations. My assumption is that I am doing something wrong while traversing the array, might be missing some calculations for subproblems, but not able to find the issue to fix it.

Problem Statement:

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

My Solution:


/* 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;
    }

MBo MBo · Accepted Answer · 2021-09-21T08:49:38

Seems you don't update dp array in the case of existing value

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

Perhaps you need to choose best from three variants

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

But we can solve this problem without recursion using bottom-up order (not checked)

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];
}

Minimum Coin Change Top Down DP with 1D array

1 Answers