Leetcode 322. 零钱兑换
心路历程：
这道题和上一道完全平方数的和基本上一摸一样，甚至比上一道题还简单，基于dp的建模：
状态：当前的目标总金额
动作：选哪一个硬币
返回值：凑成该目标总金额的最少硬币个数
这道题如果硬币不能重复使用的话，那就是一个回溯问题，优化只能靠剪枝不能靠记忆化搜索了。因为动作选择完需要再append回去。
注意的点：
1、注意判断不能组成的情况并返回无穷
2、注意在返回时将无穷变为-1
解法：动态规划
class Solution:def coinChange(self, coins: List[int], amount: int) -> int:@cachedef dp(x): # 组成x的最少硬币个数if x == 0: return 0if x < 0: return float('inf')# 候选动作集合nonlocal coins# 状态转移res = []for coin in coins:res.append(dp(x-coin) + 1)return min(res)ans = dp(amount)if ans == float('inf'): return -1else: return ans