322. Coin Change

/*
 * Good example [2, 3, 6], amount: 13
 * 6, (6), 3, (3), 2, 2
 *
 * [186, 419, 83, 408], amount: 6249
 *
 * Shoving the biggest possible and then smaller and smaller doesn't work:
 * See
 * [1, 5, 10, 11], amount: 15
 * That would result in [11, 1, 1, 1, 1]
 * Optimum: [10, 5]
 *
 * DP SOLUTION:
 * Build up min coin needed from 0 -> amount
 * At each step, ask what the minimum number of coins would be
 * by using each of the different type of coins
 */

class Solution {

  public int coinChange(int[] coins, int amount) {
    int[] minCoins = new int[amount + 1];
    minCoins[0] = 0;

    for(int i = 1; i <= amount; i++) {
      int min = Integer.MAX_VALUE;

      for(int coin : coins) {
        if (i - coin >= 0 && // Within bounds
            minCoins[i - coin] != -1 && // Able to use previous solution
            minCoins[i - coin] < min) { // New minimum

          min = minCoins[i - coin];
        }
      }

      minCoins[i] = min == Integer.MAX_VALUE ? -1 : min + 1;
    }

    return minCoins[amount];
  }
}