> For the complete documentation index, see [llms.txt](https://jaywin.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jaywin.gitbook.io/leetcode/solutions/0322-coin-change.md).

# 0322. Coin Change

<https://leetcode.com/problems/coin-change>

## Description

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
```

**Example 4:**

```
**Input:** coins = [1], amount = 1
**Output:** 1
```

**Example 5:**

```
**Input:** coins = [1], amount = 2
**Output:** 2
```

**Constraints:**

* `1 <= coins.length <= 12`
* `1 <= coins[i] <= 231 - 1`
* `0 <= amount <= 104`

## ac: dp

```java
class Solution {
    public int coinChange(int[] coins, int amount) {
        // edge cases
        if (coins == null || coins.length == 0 || amount <= 0) return 0;

        // DP
        int[] dp = new int[amount+1];
            // init
        for (int i : coins) {
            if (i <= amount) dp[i] = 1;
        }
            // iterate
        for (int i = 1; i <= amount; i++) {
            if (dp[i] != 0) continue;
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < coins.length; j++) {
                int prev = i - coins[j];
                if (prev <= 0 || dp[prev] == -1) continue;
                min = Math.min(min, dp[prev] + 1);
            }
            dp[i] = min == Integer.MAX_VALUE ? -1 : min;
        }


        // res
        return dp[amount];
    }
}

/*
state: dp[i] means fewest coins for i amount
func: dp[i], iterate coins, i - coin, get minimun
init: dp[coin] = 1
result: last one

*/
```

This one is a little bit concise

```java
class Solution {
    public int coinChange(int[] coins, int amount) {
        // edge cases
        if (coins == null || coins.length == 0 || amount <= 0) return 0;

        int[] dp = new int[amount+1];
        // init
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;

        // iterate
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (coins[j] <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }

        // res
        return dp[amount] > amount ? -1 : dp[amount];
    }
}
```