递归题代码如何修改

Terence888

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

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

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

class Solution:
    def coinChange(self, coins: List[int], 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为负时返回上一层级节点

FishC

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

以下是修改后的代码：

class Solution:
    def coinChange(self, coins: List[int], 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

        试试这个代码

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