打卡群刷题总结0926——零钱兑换

题目：322. 零钱兑换

链接：https://leetcode-cn.com/problems/coin-change

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。 示例 1: 输入: coins = [1, 2, 5], amount = 11 输出: 3 解释: 11 = 5 + 5 + 1 示例 2: 输入: coins = [2], amount = 3 输出: -1 说明: 你可以认为每种硬币的数量是无限的。

解题：

1、dp问题。公式为：dp[i] = max(dp[i], dp[i - coin] +1)，其中 ，coin为每一枚硬币。

代码：

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [sys.maxsize] * (amount + 1)
        dp[0] = 0
        coins = sorted(coins)
        for i in range(1, amount + 1):
            for coin in coins:
                if amount - coin < 0:
                    break
                dp[i] = min(dp[i], dp[i - coin] + 1)
        return -1 if dp[-1] == sys.maxsize else dp[-1]

PS：刷了打卡群的题，再刷另一道题，并且总结，确实耗费很多时间。如果时间不够，以后的更新会总结打卡群的题。

PPS：还是得日更呀，总结一下总是好的。