难度: Medium
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins =[1, 2, 5], amount =11输出：3解释：11 = 5 + 5 + 1
示例 2：
输入：coins =[2], amount =3输出：-1
示例 3：
输入：coins = [1], amount = 0 输出：0
提示：
1 <= coins.length <= 121 <= coins[i] <= 231 - 10 <= amount <= 104运行时间: 1336 ms
内存: 14.9 MB
from typing import List
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
# memo = dict()
# def dp(memo, n):
# if n in memo:
# return memo[n]
# if n == 0:
# return 0
# if n < 0:
# return -1
# res = float('INF')
# for coin in coins:
# subproblem = dp(memo, n-coin)
# if subproblem == -1:
# continue
# res = min(res, 1+subproblem)
# memo[n] = res if res != float('INF') else -1
# return memo[n]
# return dp(memo, amount)
dp = [amount+1] * (amount+1)
dp[0] = 0
for i in range(0, len(dp)):
for coin in coins:
if i - coin < 0:
continue
dp[i] = min(dp[i], 1+dp[i-coin])
return -1 if dp[amount] == amount+1 else dp[amount]
这个题解使用了动态规划的方法来解决零钱兑换问题。主要思路是：对于给定的总金额 amount，计算凑成该金额所需的最少硬币数量。定义 dp[i] 表示凑成金额 i 所需的最少硬币数量。对于每个金额 i，遍历所有可用硬币面额 coin，尝试使用该面额的硬币，并将所需硬币数量更新为 dp[i] 和 1 + dp[i-coin] 中的较小值。最终 dp[amount] 即为凑成总金额所需的最少硬币数量。
时间复杂度: O(amount * len(coins))
空间复杂度: O(amount)
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
# 定义 dp 数组，初始值为 amount+1（一个不可能达到的值）
dp = [amount+1] * (amount+1)
# base case: 凑成金额 0 需要 0 个硬币
dp[0] = 0
# 遍历所有金额
for i in range(0, len(dp)):
# 遍历所有可用硬币面额
for coin in coins:
# 如果当前金额小于硬币面额，跳过
if i - coin < 0:
continue
# 更新凑成当前金额所需的最少硬币数量
dp[i] = min(dp[i], 1+dp[i-coin])
# 如果 dp[amount] 的值没有被更新，说明无法凑成总金额，返回 -1
return -1 if dp[amount] == amount+1 else dp[amount]
在初始化dp数组时，所有元素的初始值设置为amount+1，这是因为amount+1代表一个比任何实际需要的硬币数都大的值，实际上是一个无效值或无法达到的值。使用这样的值可以方便地在后续的动态规划过程中通过比较来更新最小硬币数。如果我们使用其他更小的值，可能导致无法正确反映凑成某金额需要的真实硬币数量。设置为amount+1就是为了确保dp[i]只有在找到有效的硬币组合时才被更新。
凑成金额0的硬币数需要设置为0是因为，如果不需要任何金额，自然也就不需要任何硬币。这是动态规划解决问题的基础情况，即‘base case’。设置dp[0] = 0是为了在开始动态规划时有一个正确的起点，因为凑成任何正金额至少需要一枚硬币，而凑成0金额则不需要任何硬币。
如果dp[amount]的值等于amount+1，返回-1是因为amount+1是一个初始化时设置的无效值，如果在动态规划的过程中这个值没有被更新，说明没有找到任何有效的硬币组合来凑成该金额。这种情况下，dp[amount]保持为amount+1意味着凑成总金额amount是不可能的，因此返回-1来表示无法凑成指定金额。
在动态规划的更新公式中，使用1 + dp[i-coin]来更新dp[i]是因为这里的1代表使用了一枚当前遍历到的coin硬币。dp[i-coin]代表在使用这枚硬币之前，凑成金额i-coin所需的最少硬币数量。因此1 + dp[i-coin]就是加上这枚硬币之后，总的硬币数量。选择这种更新方式是为了确保每一步都考虑到使用每一种可能的硬币，从而找出凑成金额i的最少硬币数。