### The Problem

You are given an integer array `coins` representing coins of different denominations and an integer `amount` representing a total amount of money.

Return 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`.

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

Check LeetCode link for more details and example input & output.

### Dynamic Programming Solutions

#### A Top Down Approach

A Java solution.

``````  public int coinChange(int[] coins, int amount) {
return coinChange(coins, amount, new HashMap<>());
}

int coinChange(int[] coins, int amount, Map<Integer, Integer> dp) {
if (amount < 0) {
return -1;
}
if (amount == 0) { // a base case & edge case
return 0;
}
if (dp.get(amount) != null) {
return dp.get(amount);
}

int min = amount + 1; // ā
for (int i = 0; i < coins.length; i++) {
int changes = 1 + coinChange(coins, amount - coins[i], dp);
// `changes == 0` meaning the above `coinChange` call return `-1`,
// no need to update `min` in this case
if (changes != 0 && changes < min) {
min = changes;
}
}
// if `min` stays at its initial value, it means no answer for input `amount`
if (min == amount + 1) {
min = -1;
}

dp.put(amount, min);

return min;
}
``````

For initial value of `min`, (line ā ), `amount + 1` is big enough. Because even if coin `1` exists, the maximum value of `changes` is `amount`.

#### A Bottom Up Approach

``````dp[i] = min(1 + dp[i - coins[0]], 1 + dp[i - coins[1]], 1 + dp[i - coins[2]], ...)
``````

`dp[i]` is the answer of the sub problem āiā, where `i` is the input of the amount for this sub problem.

Base case is `dp[0] = 0`.

``````  public int coinChange(int[] coins, int amount) {
// array length is `amount + 1`, since we are to calculate dp[amount]
int[] dp = new int[amount + 1];
// set initial value. why `amount + 1`, see comments above.
Arrays.fill(dp, amount + 1);

dp[0] = 0; // the base case and the edge case

for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.length; j++) {
int index = i - coins[j];
// to avoid out-of-bound when index is negative
if (index >= 0) {
dp[i] = Math.min(dp[i], 1 + dp[index]);
}
}
}

// if it's still the initial value, return -1
if (dp[amount] == amount + 1) {
return -1;
}

return dp[amount];
}
``````

The time complexity is `O(n*m)`, `n` is `amount`, `m` is number of `coins`.