Simple Iterative O(n^2) solution.


  • 0
    S

    Explanation:
    First of all, we mark that for state 0 (sum 0) we have found a solution with a minimum number of 0 coins. We then go to sum 1. First, we mark that we haven’t yet found a solution for this one (a value of Infinity would be fine). Then we see that only coin 1 is less than or equal to the current sum. Analyzing it, we see that for sum 1-V1= 0 we have a solution with 0 coins. Because we add one coin to this solution, we’ll have a solution with 1 coin for sum 1. It’s the only solution yet found for this sum. We write (save) it. Then we proceed to the next state – sum 2. We again see that the only coin which is less or equal to this sum is the first coin, having a value of 1. The optimal solution found for sum (2-1) = 1 is coin 1. This coin 1 plus the first coin will sum up to 2, and thus make a sum of 2 with the help of only 2 coins. This is the best and only solution for sum 2. Now we proceed to sum 3. We now have 2 coins which are to be analyzed – first and second one, having values of 1 and 3. Let’s see the first one. There exists a solution for sum 2 (3 – 1) and therefore we can construct from it a solution for sum 3 by adding the first coin to it. Because the best solution for sum 2 that we found has 2 coins, the new solution for sum 3 will have 3 coins. Now let’s take the second coin with value equal to 3. The sum for which this coin needs to be added to make 3 , is 0. We know that sum 0 is made up of 0 coins. Thus we can make a sum of 3 with only one coin – 3. We see that it’s better than the previous found solution for sum 3 , which was composed of 3 coins. We update it and mark it as having only 1 coin. The same we do for sum 4, and get a solution of 2 coins – 1+3. And so on.

     public int coinChange(int[] coins, int amount) {
    	       int[] min = new int[amount+1];
    	        Arrays.fill(min, Integer.MAX_VALUE-1);
    	        min[0] = 0;
    	        for(int i=1;i<=amount;i++){
    	            for(int coin:coins){
    	                if(i>=coin && min[i-coin]+1<min[i]) 
    	                    min[i] = min[i-coin]+1;
    	            }
    	            // System.out.println(min[i]+": "+i);
    	        }
    	        return (min[amount]==Integer.MAX_VALUE-1)?-1:min[amount];
    	    }
    	    
    

Log in to reply
 

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