LeetCode: 322. Coin Change

This is a typical DP problem.

At first, one should think of backtracking all the cases.

That way, you can find the solution but it isn't efficient.

In the meantime, you should notice that you will calculate for the same amount repeatedly when backtracking all the cases.

Inspired by that idea, apply DP there.

Below is the code.

INF = int(1e9)
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        self.dp = {}
        if self.dfs(coins, amount) == INF:
            return -1
        return self.dfs(coins, amount)
        
    def dfs(self, coins, amount):
        if amount == 0:
            return 0
        if amount in self.dp:
            return self.dp[amount]
        ret = INF
        for coin in coins:
            if amount - coin >= 0:
                ret = min(ret, self.dfs(coins, amount-coin) + 1)
        self.dp[amount] = ret
        return ret

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