322. 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.

You may assume that you have an infinite number of each kind of coin.

My Answer 1: Wrong Answer (46 / 182 test cases passed.)

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        if amount == 0:
            return 0
        if amount in coins:
            return 1
        
        coins.sort()
        result = []
        i = -1
        
        while i != (len(coins)+1)*(-1):
            if sum(result)+coins[i] == amount:
                result.append(coins[i])
                break
                
            if sum(result)+coins[i] < amount and coins[i] < amount:
                result.append(coins[i])
                
            else:
                i -= 1
        
        if len(result) == 0 or sum(result) != amount:
            return -1
        
        return len(result)

하다 말긴 했는데..

coins 를 순서대로 정렬한 후 젤 큰 값부터 result 에 넣어서 sum 값 비교하는 식으로 했는데
반복문을 한 번 더 써야할 것 같다.

backtracking 을 써야하나..

Dynamic programming - Top down

Solution: Runtime: 2220 ms - 10.82% / Memory Usage: 17.3 MB - 17.93%

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        if amount <= 0:
            return 0
        dp = {}
        result = self.helper(coins, amount, dp)
        return -1 if result == float('inf') else result
    
    def helper(self, coins, amount, dp):
        if amount < 0:
            return float('inf')
        if amount == 0:
            return 0
        if amount in dp:
            return dp[amount]
        for i in range(len(coins)):
            use_ci = 1 + self.helper(coins, amount - coins[i], dp)
            if amount not in dp:
                dp[amount] = use_ci
            else:
                dp[amount] = min(dp[amount], use_ci)       
        return dp[amount]

Dynamic programming - Bottom up

Solution: Runtime: 1092 ms - 88.04% / Memory Usage: 14.6 MB - 42.83%

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0
        
        for coin in coins:
            for x in range(coin, amount + 1):
                dp[x] = min(dp[x], dp[x - coin] + 1)
        return dp[amount] if dp[amount] != float('inf') else -1 

DP 를 가장 많이 쓴다..
Top down 보단 Bottom up 이 더 효율이 좋음

근데 어렵ㅠㅠㅠㅠ