CoinChange.java

public int coinChangeDP(int[] coins, int amount) {
    if (coins == null || coins.length == 0) {
        return -1;
    }
    // lookup contains the min number of coins needed to reach the amount(i.e., index)
    int[] lookup = new int[amount + 1];
    lookup[0] = 0;

    for (int i = 1; i <= amount; i++) {
        int min = Integer.MAX_VALUE;
        for (int coin : coins) {
            if (i >= coin && lookup[i - coin] != -1) {
                min = Math.min(min, lookup[i - coin] + 1);
            }
        }
        lookup[i] = (min == Integer.MAX_VALUE ? -1 : min);
    }

    return lookup[amount];
}