322. Coin Change

Loading...LeetCode

应该最典型的dp了。

We note that this problem has an optimal substructure property, which is the key piece in solving any Dynamic Programming problems. In other words, the optimal solution can be constructed from optimal solutions of its subproblems.

状态转换方程——凑n需要的最少硬币数，等于凑n-t需要的最小硬币数加1，t是coins内小于n的任意面值：

$$f(n) = f(n-t) + 1 \quad for \; t\; in\;<coins>\;if\;n>=t$$

01/07/2021 update:

更新 bottom-up 的解法，个人觉得更直观、好理解一点，也容易写得简短。

top-down

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        if not amount: return 0
        dp = {n:1 for n in coins}
        threshold = min(coins)
        
        def fewestCoins(n):
            if n < threshold: return float('inf')
            if n in dp: return dp[n]
            else:     
                dp[n] = min([fewestCoins(n-c) for c in coins if c < n]) + 1
                return dp[n]
        
        res = fewestCoins(amount)
        return res if res <= amount else -1

bottom-up

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [0 for _ in range(amount+1)]
        
        for n in range(1, amount+1):
            prev = [x for x in [dp[n-c] for c in coins if n >= c] if x >= 0]
            dp[n] = min(prev) + 1 if prev else -1
        
        return dp[-1]