递归题代码如何修改

Terence888

322. 零钱兑换
中等
相关标签
相关企业
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。
题目描述如上，代码如下

1. class Solution:
   
2.     def coinChange(self, coins: List[int], amount: int) -> int:
   
3.         res = float('inf') #比较数组长度，存放最小的
   
4.         ans = [] #存放每个满足条件的数组
   
5.         def dfs(coins,target):
   
6.             
   
7.             for coin in coins:        
   
8.                     ans.append(coin)
   
9.                     target -= coin
   
10.                     if target == 0:
    
11.                         res = min(res,len(ans))
    
12.                     elif target < 0:
    
13.                         return
    
14.                     else:
    
15.                         dfs(coins,target)
    
16.             return res
    
17.         dfs(coins,amount)
    
18.                
    
19. 
    

复制代码

怎么修改代码以使target为负时返回上一层级节点

FishC

你可以通过在递归函数中加入回溯的步骤来解决这个问题。当 `target` 为负时，需要从当前层级返回，同时将之前尝试加入 `ans` 的硬币再移除掉。

以下是修改后的代码：

1. class Solution:
   
2.     def coinChange(self, coins: List[int], amount: int) -> int:
   
3.         self.res = float('inf')  # 使用实例变量来存储全局最小值
   
4.         ans = []  # 存放每个满足条件的数组
   
5. 
   
6.         def dfs(target):
   
7.             # 当 target 为负数时，直接返回
   
8.             if target < 0:
   
9.                 return
   
10. 
    
11.             # 当 target 为零时，更新最小硬币数量
    
12.             if target == 0:
    
13.                 self.res = min(self.res, len(ans))
    
14.                 return
    
15. 
    
16.             for coin in coins:
    
17.                 ans.append(coin)  # 选中一个硬币
    
18.                 dfs(target - coin)  # 继续递归搜索
    
19.                 ans.pop()  # 回溯：移除最后一个硬币，返回上一层级
    
20. 
    
21.         dfs(amount)
    
22.         
    
23.         # 如果 res 没有被更新，返回 -1
    
24.         return self.res if self.res != float('inf') else -1

复制代码

这里的关键是加入了 `ans.pop()`，这一步用于在递归返回时移除上一次选中的硬币，以确保在新的递归路径中可以尝试不同的组合。这种回溯的手法可以有效避免重复和不必要的计算。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

jackz007

        试试这个代码

1. class Solution:
   
2.     def coinChange(self , coins: list[int] , amount: int) -> int:
   
3.         coins . sort(reverse = True)
   
4.         e , i , r = [0 for _ in range(len(coins))] , 0 , amount
   
5.         while r > 0 and i < len(coins) :
   
6.             if r >= coins[i] :
   
7.                 e[i] , r = r // coins[i] , r % coins[i]
   
8.             i += 1
   
9.         return sum(e) if not r else -1

复制代码