介绍国外的网站有什么不同/广州网络推广万企在线

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

-----------------------------------------------------------------------------

思路：通过 "递归+回测" 的组合来找到最小值的方式超时，这里需要用 "动态规划" 来处理。dp_array[i]表示组成数字i所需要的最小的硬币数。

解法1#：动态规划

class Solution(object):def coinChange(self, coins, amount):""":type coins: List[int]:type amount: int:rtype: int"""if (not coins) or (amount < min(coins)):return -1# 构建一个动态数组dp_array dp_array = [0] + [amount+1]*amountfor i in range(1, amount+1):for j in range(len(coins)):if i >= coins[j]:# 这里需要比较: dp_array[i]代表使用coins[j]，dp_array[i-coins[j]]+1代表不使用coins[j]dp_array[i] = min(dp_array[i], dp_array[i-coins[j]]+1)# dp_array[-1] > amount表示组合拼接的总值比amount大，不符合要求return -1 if dp_array[-1] > amount else dp_array[-1]

参考：

https://blog.csdn.net/qq_38575545/article/details/86421175

https://blog.csdn.net/zw159357/article/details/82664026