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)

長いこと話しましたが…
コインを順番に並べた後、最大値から結果に入れ、値と比較します.
もう一度複文を書くべきだと思います.
遡及するか...

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..
Boottom upはTop downより効率が高い
でも難しい