本文共 944 字，大约阅读时间需要 3 分钟。

LeetCode.jpg

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

Python3 实现

动态规划

# @author:leacoder# @des:  动态规划 零钱兑换class Solution:    def coinChange(self, coins: List[int], amount: int) -> int:        if amount < 0 :    return -1        DP = [amount + 1]*(amount + 1) #DP[i] 表示 总金额 为 i 时的最少硬币数，极限情况硬币数为 amount 不可能为 amount + 1        DP[0] = 0 # 初始  下面 DP[i - coin]  中 i - coin = 0时        for i in range(1,amount+1): # 总金额 1 到 amount 的循环            for coin in coins: # 不同面额遍历                if coin <= i: # 面额小于总金额                    DP[i] = min(DP[i],DP[i - coin] + 1) # DP方程 类似70. 爬楼梯；                 if DP[amount] == amount+1:             return -1        else:            return DP[amount]

GitHub链接：

知乎个人首页：

简书个人首页：

个人Blog:

欢迎大家来一起交流学习

转载地址：https://blog.csdn.net/leacock1991/article/details/101467261 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！