## [DP] Minimum number of coins need for a specific amount

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]; }

## 0 comments:

## Post a Comment