Easy Java solution with Knapsack approach and Explanation(21 ms)


  • 0
    S

    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.

    int[] dp = new int[amount+1];
            Arrays.fill(dp, Integer.MAX_VALUE-1);
            dp[0] = 0;
            for(int coin:coins){
                for(int i=coin;i<=amount;i++){
                    if(dp[i-coin]+1<dp[i])
                        dp[i] = dp[i-coin]+1;
                }
            }
            return (dp[amount]==Integer.MAX_VALUE-1)?-1:dp[amount];
        }
    

Log in to reply
 

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