# 322. Coin Change

## Problem 322

<https://leetcode.com/problems/coin-change/>\
You are given coins of different denominations and a total amount of money amount. Write a function to compute 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`.

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

## Solution

* `float('inf')` means infinity large

{% tabs %}
{% tab title="DFS" %}

```python
class Solution:
    def coinChange(self, coins, amount):
        coins.sort( reverse = True)
        lenc, self.min_step = len(coins), float('inf')
        
        def dfs( point, amo , count ):
            if not amo: #amount != 0
                self.min_step = min( self.min_step, count )
            for i in range( point, lenc ):
                if coins[i] <= amo < coins[i] * (self.min_step - count):
                    dfs( i, amo-coins[i], count+1 )
            
        for i in range( lenc ):
            dfs( i, amount, 0 )
    
        return [self.min_step, -1][ self.min_step == float('inf') ]
```

```python
class Solution_interative:
    def coinChange(self, coins, amount):
        coins.sort()
        lenc, min_steps = len(coins), float('inf')
        dfs_stack = [ (0, 0, lenc) ]
        
        while len(dfs_stack) != 0:
            steps, value_now, coins_num = dfs_stack.pop()
            if value_now == amount:
                min_steps = min( min_steps, steps )
            if value_now > amount or amount - value_now > coins[ coins_num-1 ] * (min_steps - steps):
                continue
            for coinnum, coin in enumerate( coins[:coins_num] ):
                dfs_stack.append( (steps+1, value_now + coin, coinnum + 1) )
                
        return min_steps if min_steps != float('inf') else -1
```

{% endtab %}

{% tab title="BFS" %}

```python
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        if amount == 0:
            return 0
        
        visited = [False]*(amount+1)
        visited[0] = True
        coin_num = 0
        value_now, value_next = [0], []
        
        while value_now:
            coin_num += 1
            for value in value_now:
                for coin in coins:
                    newvalue = value + coin
                    if newvalue == amount:
                        return coin_num
                    elif newvalue > amount:
                        continue
                    elif not visited[newvalue]:
                        visited[newvalue] = True
                        value_next.append( newvalue )
            value_now, value_next = value_next, []
            
        return -1
```

{% endtab %}

{% tab title="" %}

```python
class Solution:
    def coinChange(self, coins, amount):
        value_list = [amount+1] * (amount+1)
        value_list[0] = 0
        
        for i in range( 1, amount+1 ):
            for coin in coins:
                if i >= coin:
                    value_list[i] = min( value_list[i-coin] + 1, value_list[i] )
        
        return -1 if value_list[amount] == amount + 1 else value_list[amount]
```

```python
class SolutionII:
    def coinChange(self, coins: List[int], amount: int) -> int:
        MAX = float( 'inf' ) #infinite large
        coin_num = [0] + [MAX]*amount
        
        for i in range(1,amount+1):
            coin_num[i] = min( [ coin_num[i - c]  if  i - c >=0 else MAX for c in coins ] ) + 1
        

        return [coin_num[amount], -1][coin_num[amount]==MAX]
```

{% endtab %}
{% endtabs %}