LeetCode 322. Coin Change问题Python DFS解法异常排查求助

你的代码逻辑本身没有错误，之所以观察不到remainder == 0的分支被触发，是因为未做记忆化优化的纯暴力DFS时间复杂度为指数级，针对amount=100的输入计算量过大，程序长时间处于递归搜索状态，你无法等到它运行到终止条件就误以为没有触发对应分支。

以你给出的coins=[1,2,5]、amount=100为例，每个递归节点会产生3个分支，递归深度最高可达100层，整体计算量达到3^100量级，普通消费级硬件不可能在短时间内跑完这个计算量。

你可以将输入的总金额改为更小的数值测试，比如amount=3，运行后即可观察到remainder == 0的分支正常触发，程序也能返回正确结果2。

要让代码能处理大数值的总金额，需要添加记忆化缓存，避免重复计算相同剩余金额的最少硬币数。同时你也可以直接返回最少硬币个数而非整个组合，进一步降低内存消耗和运行耗时，优化后的代码示例如下：

from typing import List
from functools import lru_cache

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:      
        @lru_cache(maxsize=None)
        def dfs(remainder):
            if remainder < 0:
                return float('inf')
            if remainder == 0:
                return 0         
            min_count = float('inf')
            for num in coins:
                res = dfs(remainder - num)
                if res != float('inf'):
                    min_count = min(min_count, res + 1)
            return min_count       
        
        res = dfs(amount)
        return -1 if res == float('inf') else res

s = Solution()
print(s.coinChange([1,2,5], 100)) # 输出20，符合预期

内容的提问来源于stack exchange，提问作者Yilmaz