心路历程这道题和上一道完全平方数的和基本上一摸一样甚至比上一道题还简单基于dp的建模状态当前的目标总金额动作选哪一个硬币返回值凑成该目标总金额的最少硬币个数这道题如果硬币不能重复使用的话那就是一个回溯问题优化只能靠剪枝不能靠记忆化搜索了。因为动作选择完需要再append回去。注意的点1、注意判断不能组成的情况并返回无穷2、注意在返回时将无穷变为-1解法动态规划建议背包问题还是用递归动态规划classSolution:defcoinChange(self,coins:List[int],amount:int)-int:cachedefdp(x):# 组成x的最少硬币个数ifx0:return0ifx0:returnfloat(inf)# 候选动作集合nonlocalcoins# 状态转移res[]forcoinincoins:res.append(dp(x-coin)1)returnmin(res)ansdp(amount)ifansfloat(inf):return-1else:returnans数组动态规划的转换逻辑fromtypingimportListclassSolution:defcoinChange(self,coins:List[int],amount:int)-int:# dp[i] 表示凑出金额 i 所需的最少硬币个数# 初始化为一个很大的数表示不可达INFfloat(inf)dp[INF]*(amount1)dp[0]0# 凑出0需要0个硬币# 从小到大计算每个金额的最优解foriinrange(1,amount1):forcoinincoins:ifi-coin0:# 如果能用这枚硬币看看是否更优dp[i]min(dp[i],dp[i-coin]1)return-1ifdp[amount]INFelsedp[amount]
Leetcode 322. 零钱兑换
心路历程这道题和上一道完全平方数的和基本上一摸一样甚至比上一道题还简单基于dp的建模状态当前的目标总金额动作选哪一个硬币返回值凑成该目标总金额的最少硬币个数这道题如果硬币不能重复使用的话那就是一个回溯问题优化只能靠剪枝不能靠记忆化搜索了。因为动作选择完需要再append回去。注意的点1、注意判断不能组成的情况并返回无穷2、注意在返回时将无穷变为-1解法动态规划建议背包问题还是用递归动态规划classSolution:defcoinChange(self,coins:List[int],amount:int)-int:cachedefdp(x):# 组成x的最少硬币个数ifx0:return0ifx0:returnfloat(inf)# 候选动作集合nonlocalcoins# 状态转移res[]forcoinincoins:res.append(dp(x-coin)1)returnmin(res)ansdp(amount)ifansfloat(inf):return-1else:returnans数组动态规划的转换逻辑fromtypingimportListclassSolution:defcoinChange(self,coins:List[int],amount:int)-int:# dp[i] 表示凑出金额 i 所需的最少硬币个数# 初始化为一个很大的数表示不可达INFfloat(inf)dp[INF]*(amount1)dp[0]0# 凑出0需要0个硬币# 从小到大计算每个金额的最优解foriinrange(1,amount1):forcoinincoins:ifi-coin0:# 如果能用这枚硬币看看是否更优dp[i]min(dp[i],dp[i-coin]1)return-1ifdp[amount]INFelsedp[amount]
