🟡 剑指 Offer II 103. 最少的硬币数目

LeetCode 提示

题目难度 中等

原题链接 🔗 leetcode

题解 1.正向DP.py

class Solution:    def coinChange(self, coins: List[int], amount: int) -> int:        if amount == 0:            return 0
        if len(coins) == 1:            return -1 if amount % coins[0] else amount // coins[0]
        dfs = [0] + [-1] * (amount)
        for step in range(1, amount+1):            curMin = amount + 1            for coin in coins:                if step-coin >= 0 and dfs[step-coin] >= 0:                    curMin = min(curMin, dfs[step-coin] + 1)            dfs[step] = curMin if curMin < amount+1 else -1
        return dfs[-1]