<reponame>sailikhithk/tech-interview-prep<filename>problems/coin-change.py
# DP
class Solution(object):
    def coinChange(self, coins, amount):
        dp = [float('inf')]*(amount+1)
        
        if amount==0: return 0
        
        dp[0] = 0
        for coin in coins:
            if coin<=amount:
                dp[coin] = 1
            
        for a in xrange(amount+1):
            for coin in coins:
                if a-coin>=0:
                    dp[a] = min(dp[a], dp[a-coin]+1)
                    
        return dp[amount] if dp[amount]!=float('inf') else -1

# BFS
import collections
class Solution(object):
    def coinChange(self, coins, amount):
        visited = set()
        
        coins.sort(reverse=True)
        q = collections.deque([(0, 0)])
        
        while q:
            current_amount, count = q.popleft()
            
            if current_amount==amount: return count
            if current_amount>amount: continue
            if current_amount in visited: continue
            visited.add(current_amount)
            
            for coin in coins:
                q.append((current_amount+coin, count+1))
        return -1
# DP
class Solution(object):
    def coinChange(self, coins, amount):
        dp = [float('inf')]*(amount+1)
        
        if amount==0: return 0
        
        dp[0] = 0
        for coin in coins:
            if coin<=amount:
                dp[coin] = 1
            
        for a in xrange(amount+1):
            for coin in coins:
                if a-coin>=0:
                    dp[a] = min(dp[a], dp[a-coin]+1)
                    
        return dp[amount] if dp[amount]!=float('inf') else -1

# BFS
import collections
class Solution(object):
    def coinChange(self, coins, amount):
        visited = set()
        
        coins.sort(reverse=True)
        q = collections.deque([(0, 0)])
        
        while q:
            current_amount, count = q.popleft()
            
            if current_amount==amount: return count
            if current_amount>amount: continue
            if current_amount in visited: continue
            visited.add(current_amount)
            
            for coin in coins:
                q.append((current_amount+coin, count+1))
        return -1
# DP # BFS