_322.java

package com.fishercoder.solutions;

import java.util.Arrays;

/**
 * You are given coins of different denominations and a total amount of money amount. 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
 return 3 (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.
 */
public class _322 {

    public int coinChange(int[] coins, int amount) {
        if(amount < 1) return 0;
        int[] count = new int[amount];
        int result = helper(coins, amount, count);

        return result;
    }

    //remaining means the remaining coins after the last step;
    //count[remaining] means the minimum number of coins to sum up to remaining
    private int helper(int[] coins, int remaining, int[] count) {
        if(remaining < 0) return -1;//not valid case, thus, per problem description, we should return -1
        if(remaining == 0) return 0;//completed, this is also a base case for this recursive function
        if(count[remaining-1] != 0) return count[remaining-1];//already computed, so reuse it.
        int min = Integer.MAX_VALUE;
        for(int coin : coins){
            int res = helper(coins, remaining-coin, count);
            if(res >= 0 && res < min){
                min = 1+res;
            }
        }
        return count[remaining-1] = (min == Integer.MAX_VALUE) ? -1 : min;

    }

    //dp solution
    public int coinChangeDP(int[] coins, int amount) {
        int max = amount + 1;
        int [] dp = new int[max];
        Arrays.fill(dp, max);// initial the dp array with amount + 1 which is not valid case.
        dp[0] = 0;//initial first amount 0 = 0;
        for(int i = 1; i <= amount; i++) {
            for(int j = 0; j < coins.length; j++) {
                if(coins[j] <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);//the dp[coins[j]] will ba a valid case, then if dp[i - coins[j]] is  valid
                    // then we update dp[i], otherwise dp[i] = max;
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }

}