322. Coin Change - LeetCode

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.

Example 1:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

**Explanation:**

**We use dynamic programming for this problem: ****First, we try to resolve the smaller problem!**

Suppose we have numbers type of coins = [1,2,5]
We need to get minimum coins for amount 2
The smallest amount is 0 then we need 0 coin
With amount 1 we need 1 coin
With amount 2:
For case: coin 1 < 2, mean coin 1 can be used, then 1 coin
We need to calculate the coins for remain amount
The reimain amount is 2-1 = 1
No. of coin for amount 1 is 1
=> for this case we need 2 coins.
For case: coin 2 <= 2, mean coin 2 can be used, then we have 1 coin
We need to calculate the coins for remain amount
The reimain amount is 2 - 2 = 0
No. of coin for amount 0 is 0
=> for this case we need 1 coins.
compare with the previouse case, 1<2 then the answer is 1
For case 5: 5 > 2, cannot use
Then we just continue until the amount we're looking for.

**Solution:**

public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount+1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;
Arrays.sort(coins);
for (int a = 1; a <= amount; a++){
for(int i = 0; i<coins.length; i++){
if (coins[i] <= a){
int remain = a - coins[i];
int numOfCoin = 1 + dp[remain];
dp[a] = Math.min(dp[a], numOfCoin);
}
}
}
return dp[amount] > amount? -1: dp[amount];
}