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

DFS

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') ]

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

BFS

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

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]

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]