Leetcode Link: 322. 零钱兑换 - 力扣（LeetCode）
题目
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1
你可以认为每种硬币的数量是无限的。
解法一
思路：暴力递归
典型的从左到右的尝试模型
在每一位上，穷举所有可以使用当前硬币的数量。
题解：
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
# 使用 i 及 i以后的金币，返回凑成target的最少数量
@cache
def process(i, target):
if target == 0:
return 0
if i == len(coins): # 必需放这，不能放while里
return float('inf')
n = 0 # 使用当前位硬币的个数
res = float('inf')
while(target-n*coins[i]>=0):
res = min(res, process(i+1, target-n*coins[i])+n)
n += 1
return res
res = process(0, amount)
return -1 if res==float('inf') else res解法二
思路：改写成动态规划，简单。
题解
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [[float('inf') for _ in range(amount+1)] for _ in range(len(coins))]
# 初始化，填写 target == 0 的时候
for i in range(len(coins)):
dp[i][0] = 0
# 初始化，填写使用最后一个面额的时候
for tar in range(1, amount+1):
if tar % coins[-1] == 0:
dp[len(coins)-1][tar] = tar//coins[-1]
for i in range(len(coins)-2, -1, -1):
for tar in range(1, amount+1):
n = 0
while(tar-n*coins[i]>=0):
dp[i][tar] = min(dp[i][tar], dp[i+1][tar-n*coins[i]]+n)
n += 1
return -1 if dp[0][amount]==float('inf') else dp[0][amount] Attention
如果不写第二个初始化，同时改写
while为while(tar-n*coins[i]>=0 and i+1<len(coins))会报错，原因是最后一行没有无法更新。
解法三
思路： 解法一二均会超时，因为有一个循环在。 画出 dp 表的中普通情况下的依赖关系，可以进一步简化，去掉循环部分。
上图中红色依赖的下面一行的三个格子和绿色依赖的两个格子重复了，因此可以进行合并。但是注意绿色要+1。即
dp[i][tar] = min(dp[i+1][tar], dp[i][tar-coins[i]]+1)
我开始就忘记了+1
题解：
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [[float('inf') for _ in range(amount+1)] for _ in range(len(coins))]
# 初始化，填写 target == 0 的时候
for i in range(len(coins)):
dp[i][0] = 0
# 初始化，填写使用最后一个面额的时候
for tar in range(1, amount+1):
if tar % coins[-1] == 0:
dp[len(coins)-1][tar] = tar//coins[-1]
for i in range(len(coins)-2, -1, -1): #最后一行已经初始化了
for tar in range(1, amount+1): #第一列已经初始化了
if tar-coins[i] >= 0:
dp[i][tar] = min(dp[i+1][tar], dp[i][tar-coins[i]]+1) # 一定注意这里有一个 +1 ！
else:
dp[i][tar] = dp[i+1][tar]
return -1 if dp[0][amount]==float('inf') else dp[0][amount]