322. Coin Change

322。Coin Change

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

Example 3:

Input: coins = [1], amount = 0
Output: 0

Constraints:

• 1 <= coins.length <= 12

• 1 <= coins[i] <= 231 - 1

• 0 <= amount <= 104

My Solutions:

建立一个长度为amount+1的dp数组，初始值都是MAX_VALUE。对每一个总数i，遍历coins里的coin。如果i比coin值大并且dp【i-c】也不是MAX_VALUE，说明可以靠加一个硬币达到当前的总数。

class Solution {
    public int coinChange(int[] coins, int amount) {
        if (amount == 0) return 0;
        int[] dp = new int[amount + 1];
        dp[0] = 0;
        
        for (int i = 1; i <= amount; i++) {
            dp[i] = Integer.MAX_VALUE;
            for (int c : coins) {
                if (i >= c && dp[i - c] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], dp[i - c] + 1);
                }
            }
        }
        
        if (dp[amount] < Integer.MAX_VALUE) return dp[amount];
        else return -1;
    }
}