# 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:**

<pre><code><strong>Input: coins = [1,2,5], amount = 11
</strong><strong>Output: 3
</strong><strong>Explanation: 11 = 5 + 5 + 1
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: coins = [2], amount = 3
</strong><strong>Output: -1
</strong></code></pre>

**Example 3:**

<pre><code><strong>Input: coins = [1], amount = 0
</strong><strong>Output: 0
</strong></code></pre>

**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;
    }
}
```
