# 322. Coin Change

#### Medium

***

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`

#### Solution 1 :&#x20;

```python
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = {}
        dp[0] = 0
        def recursion(amount):
            if amount in dp:
                return dp[amount]
            dp[amount] = float("inf")
            for coin in coins:
                if amount - coin >= 0 :
                    dp[amount] = min(dp[amount], 1+recursion(amount-coin))
            return dp[amount]
        recursion(amount)
        return -1 if dp[amount] == float("inf") else dp[amount]
        
```

#### Solution 2 :

```python
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # For 0 amount there are 0 ways hence first element is zero
        arr = [0] + [float('inf')]*amount
        for amt in range(1, amount+1):
            for coin in coins:
                if amt-coin >= 0:
                    arr[amt] = min(arr[amt], arr[amt-coin] + 1)
        return -1 if arr[-1] == float("inf") else arr[-1]
        
```