CoinChange.java

package dynamic_programming;

/**
 * Created by gouthamvidyapradhan on 23/06/2017. 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.
 *
 * <p>Example 1: coins = [1, 2, 5], amount = 11 return 3 (11 = 5 + 5 + 1)
 *
 * <p>Example 2: coins = [2], amount = 3 return -1.
 *
 * <p>Note: You may assume that you have an infinite number of each kind of coin.
 *
 * <p>Solution: For example if you have N coins and amount equal to Q For every coin you have two
 * options i) If you chose to include this coin then, total amount reduces by the sum equivalent to
 * the value of this coin and you are left with N coins and Q = (Q - value of this coin) ii) If you
 * chose not to include this coin then, you are left with N - 1 coins (since you chose to not to
 * include this coin) and total amount is still equal to Q
 *
 * <p>Calculate recursively for each coin and possible amount Since there can be overlapping
 * sub-problems you can save the state in a 2D matrix - a typical DP approach.
 *
 * <p>For each state minimum is calculated using -> Min(1 + fn(i, amount - v[i]), fn(i + 1, amount))
 *
 * <p>Worst-case time complexity is O(N x Q) where N is the total number of coins and Q is the total
 * amount
 */
public class CoinChange {
  private int[][] DP;

  /**
   * Main method
   *
   * @param args
   * @throws Exception
   */
  public static void main(String[] args) throws Exception {
    int[] coins = {1, 2, 5};
    System.out.println(new CoinChange().coinChange(coins, 11));
  }

  public int coinChange(int[] coins, int amount) {
    DP = new int[coins.length][amount + 1];
    int result = dp(amount, 0, coins);
    if (result == Integer.MAX_VALUE - 1) return -1;
    return result;
  }

  private int dp(int amount, int i, int[] coins) {
    if (amount == 0) return 0;
    else if (i >= coins.length || amount < 0) return Integer.MAX_VALUE - 1;
    if (DP[i][amount] != 0) return DP[i][amount];
    DP[i][amount] = Math.min(1 + dp(amount - coins[i], i, coins), dp(amount, i + 1, coins));
    return DP[i][amount];
  }
}