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

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

  5:18 PM    admin

---

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