*Java* Both iterative and recursive solutions with explanations


  • 52
    E

    #Recursive Method:#
    The idea is very classic dynamic programming: think of the last step we take. Suppose we have already found out the best way to sum up to amount a, then for the last step, we can choose any coin type which gives us a remainder r where r = a-coins[i] for all i's. For every remainder, go through exactly the same process as before until either the remainder is 0 or less than 0 (meaning not a valid solution). With this idea, the only remaining detail is to store the minimum number of coins needed to sum up to r so that we don't need to recompute it over and over again.

    Code in Java:

    public class Solution {
    public int coinChange(int[] coins, int amount) {
        if(amount<1) return 0;
        return helper(coins, amount, new int[amount]);
    }
    
    private int helper(int[] coins, int rem, int[] count) { // rem: remaining coins after the last step; count[rem]: minimum number of coins to sum up to rem
        if(rem<0) return -1; // not valid
        if(rem==0) return 0; // completed
        if(count[rem-1] != 0) return count[rem-1]; // already computed, so reuse
        int min = Integer.MAX_VALUE;
        for(int coin : coins) {
            int res = helper(coins, rem-coin, count);
            if(res>=0 && res < min)
                min = 1+res;
        }
        count[rem-1] = (min==Integer.MAX_VALUE) ? -1 : min;
        return count[rem-1];
    }
    }
    

    #Iterative Method:#
    For the iterative solution, we think in bottom-up manner. Suppose we have already computed all the minimum counts up to sum, what would be the minimum count for sum+1?

    Code in Java:

    public class Solution {
    public int coinChange(int[] coins, int amount) {
        if(amount<1) return 0;
        int[] dp = new int[amount+1];
        int sum = 0;
        
    	while(++sum<=amount) {
    		int min = -1;
        	for(int coin : coins) {
        		if(sum >= coin && dp[sum-coin]!=-1) {
        			int temp = dp[sum-coin]+1;
        			min = min<0 ? temp : (temp < min ? temp : min);
        		}
        	}
        	dp[sum] = min;
    	}
    	return dp[amount];
    }
    }
    

    If you are interested in my other posts, please feel free to check my Github page here: https://github.com/F-L-A-G/Algorithms-in-Java


  • 9
    K

    Nice Solution, You can in fact, Improve it by early pruning if you sorted the coins array beforehand.
    so that in the iterative solution

    if the sum < coin you break from the inner loop.
    

    Code:

    public class Solution {
    public int coinChange(int[] coins, int amount) {
        if(amount<1) return 0;
        int L = coins.length;
        int[] dp = new int[amount+1];
        int sum = 0;
    
        // Modification.
        Arrays.sort(coins);
    
        while(++sum<=amount) {
            int min = -1;
            for(int coin : coins) {
                 // Modification
                if(sum < coin) break;
                if(dp[sum-coin]!=-1) {
                    int temp = dp[sum-coin]+1;
                    min = min<0 ? temp : (temp < min ? temp : min);
                }
            }
            dp[sum] = min;
        }
        return dp[amount];
    }
    }

  • 0
    E

    Early pruning is a nice idea if coins are spread out in a relatively large range. For example, if coins=[99, 50, 11, 4, 1], sorting does save some work when amount-sum becomes less than 100.


  • 0
    Y

    You didn't use int L in your iterative method.


  • 0
    E

    You are right :-(


  • 1
    Z

    The question is: if I can use a HashMap to do the memoization, it gives me TLE. Functionally your int[amount+1] works same as HashMap. It is not the logic problem.
    This might tell that HashMap is O(1) query if it gets bigger.


  • 0
    E
    This post is deleted!

  • 0
    C

    I think your recursive solution will not pass the following case.
    [1]
    2147483647, in this case count[2147483647 - 1] should be 2147483647, but this line (count[rem-1] = (min==Integer.MAX_VALUE) ? -1 : min;) would make the answer be -1.


  • 0
    S

    A simple thing to clarify GWTW: for the iterative approach, if u define the 'int[] count' as a global variable instead of a parameter to pass everywhere, there won't be much difference other than distaste of having a global var, right? or am I missing something important? Thanks!


  • 1

    @chs5003
    I just tried this extreme case with the code posted in the thread. Got Memory Limited Exceed, seems like the recursion went too deep that the stack cannot hold that much. Anyway, I think you are right for the extreme case.


  • 0
    C

    @kekezi now it seems like two people agree with me but three disagree, but no one bothers to explain why he/she doesn't agree.


  • 0
    This post is deleted!

  • 0
    X

    I think you should use continue; instead of break; in order to check other valid coin.


  • 0
    Y

    similar idea:

        public int coinChange(int[] coins, int amount) {
            int[] dp = new int[1 + amount];
    
            Arrays.fill(dp, -1);
            dp[0] = 0;
    
            for (int i = 1; i <= amount; ++i) {
                int min = Integer.MAX_VALUE;
                // find the minimum one.
                for(int c: coins) {
                    if (i >= c && -1 != dp[i - c]) min = Math.min(min, dp[i - c]);
                }
                if (Integer.MAX_VALUE != min) dp[i] = 1  + min;
            }
    
            return dp[amount];
        }
            
    

  • 0
    K

    I know everyone is saying that DP is the way to go for this question, but I think this is as much a classic BFS problem as it is a DP problem. Here's my BFS solution. I sort the array of coins so that I can exit the for-loop the first time we go negative.

    public class Solution {
        public int coinChange(int[] coins, int amount) {
            if (amount == 0) {
                return 0;
            }
            
            Arrays.sort(coins);
            
            Queue<Integer> queue = new LinkedList<>();
            boolean[] set = new boolean[amount + 1];
            
            queue.offer(amount);
            set[amount] = true;
            
            int currLevel = 1;
            int currLevelCount = 1;
            int nextLevelCount = 0;
            
            while (!queue.isEmpty()) {
                int curr = queue.poll();
                currLevelCount --;
                
                for (int coin : coins) {
                    int child = curr - coin;
                    if (child == 0) {
                        return currLevel;
                    } else if (child > 0 && !set[child]) {
                        queue.add(child);
                        set[child] = true;
                        nextLevelCount ++;
                    } else if (child < 0) {
                        continue;
                    }
                }
                
                if (currLevelCount == 0) {
                    currLevel ++;
                    currLevelCount = nextLevelCount;
                    nextLevelCount = 0;
                }
            }
            
            return -1;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.