322 Coin Change

You are given coins of different denominations and a total amount of moneyamount. Write a function to compute 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.

Example 1:
coins =[1, 2, 5], amount =11
return3(11 = 5 + 5 + 1)

Example 2:
coins =[2], amount =3
return-1.

Note:
You may assume that you have an infinite number of each kind of coin.

Solution)

#Dynamic programming

idea is

if dp[amount-coin] != MAX:
    dp[amount] = min(dp[amount], dp[amount-coin]+1)

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

#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 amounta, then for the last step, we can choose any coin type which gives us a remainderrwherer = a-coins[i]for alli'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 torso that we don’t need to recompute it over and over again.

Code in Java:

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 tosum, what would be the minimum count forsum+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];
     }
}