Min Coin Change Top Down Approach

I tried to solve the minimum of coins change problem on Leetcode but only passing for some tests. I used Java language and my approach is the dynamic top-down approach. I know the problem could be related to some cases that the amount can't be calculated to the given coin changes, but not sure how to fix it. Thanks, guys!

This is the problem

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

This is my solution

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



Read more here: https://stackoverflow.com/questions/68464399/min-coin-change-top-down-approach

Content Attribution

This content was originally published by Kim Ma at Recent Questions - Stack Overflow, and is syndicated here via their RSS feed. You can read the original post over there.

%d bloggers like this: