递归题代码如何修改
322. 零钱兑换中等
相关标签
相关企业
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
题目描述如上，代码如下
class Solution:
def coinChange(self, coins: List, amount: int) -> int:
res = float('inf') #比较数组长度，存放最小的
ans = [] #存放每个满足条件的数组
def dfs(coins,target):
for coin in coins:
ans.append(coin)
target -= coin
if target == 0:
res = min(res,len(ans))
elif target < 0:
return
else:
dfs(coins,target)
return res
dfs(coins,amount)
怎么修改代码以使target为负时返回上一层级节点 你可以通过在递归函数中加入回溯的步骤来解决这个问题。当 `target` 为负时，需要从当前层级返回，同时将之前尝试加入 `ans` 的硬币再移除掉。
以下是修改后的代码：
class Solution:
def coinChange(self, coins: List, amount: int) -> int:
self.res = float('inf')# 使用实例变量来存储全局最小值
ans = []# 存放每个满足条件的数组
def dfs(target):
# 当 target 为负数时，直接返回
if target < 0:
return
# 当 target 为零时，更新最小硬币数量
if target == 0:
self.res = min(self.res, len(ans))
return
for coin in coins:
ans.append(coin)# 选中一个硬币
dfs(target - coin)# 继续递归搜索
ans.pop()# 回溯：移除最后一个硬币，返回上一层级
dfs(amount)
# 如果 res 没有被更新，返回 -1
return self.res if self.res != float('inf') else -1
这里的关键是加入了 `ans.pop()`，这一步用于在递归返回时移除上一次选中的硬币，以确保在新的递归路径中可以尝试不同的组合。这种回溯的手法可以有效避免重复和不必要的计算。
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 本帖最后由 jackz007 于 2024-11-5 20:23 编辑
试试这个代码
class Solution:
def coinChange(self , coins: list , amount: int) -> int:
coins . sort(reverse = True)
e , i , r = , 0 , amount
while r > 0 and i < len(coins) :
if r >= coins :
e , r = r // coins , r % coins
i += 1
return sum(e) if not r else -1
页:
[1]