优化类零钱兑换的完全平方数问题Python实现（超时求助）

我之前实现过LeetCode的零钱兑换问题，知道完全平方数问题和它逻辑相似，唯一区别是候选数换成了[1,4,9,25…]这类完全平方数。我自己写的代码逻辑是对的，但处理大输入（比如8328）时会超时，希望能优化代码。

问题描述 #

给定整数n，返回和为n的完全平方数的最少数量。

完全平方数是指某个整数的平方，即一个整数与自身的乘积。例如1、4、9、16都是完全平方数，而3、11不是。

我的实现代码 #

class Solution:
    def numSquares(self,n:int)->int:
        nums=[]
        # 创建不超过n的完全平方数列表
        for i in range(1,n+1):
            if self.is_perfect(i):
                nums.append(i)
                print(nums)
        def dfs(target, memo={}):
            if target in memo:
                return memo[target]
            if target == 0:
                return []
            if target < 0:
                return None
            shortest_combination = None
            for num in nums:                
                remainder = target - num
                result = dfs(remainder)
                # 不能用if result，因为result可能是空列表会被判定为False
                if result != None:
                    # 拼接组合，这种写法比result+[num]更高效
                    combination = [*result, num]
                    if shortest_combination == None or len(combination) < len(shortest_combination):
                        shortest_combination = combination
            memo[target] = shortest_combination
            return shortest_combination
        return len(dfs(n))
    def is_perfect(self,n):
        for i in range(1,n+1):
            if i*i>n:
                return False
            if i*i==n:
                return True        
        return False

代码问题分析与优化方案 #

1. 完全平方数生成逻辑低效 #

原代码遍历1到n的每个数，再调用is_perfect判断是否为完全平方数，时间复杂度是O(n*sqrt(n))，完全没必要。直接遍历i从1开始，计算i²，只要i²<=n就加入列表，时间复杂度降到O(sqrt(n))，同时去掉拖慢速度的print(nums)：

nums = []
i = 1
while i*i <= n:
    nums.append(i*i)
    i += 1

2. 递归DFS存储完整组合，内存与时间开销大 #

原DFS返回完整的组合数组，但我们只需要组合的长度。存储数组会占用大量内存，拼接操作也浪费时间。修改记忆化逻辑，只存储每个target对应的最少完全平方数数量：

def dfs(target, memo={}):
    if target in memo:
        return memo[target]
    if target == 0:
        return 0
    if target < 0:
        return float('inf')
    min_count = float('inf')
    for num in nums:
        remainder = target - num
        count = dfs(remainder)
        if count != float('inf'):
            min_count = min(min_count, count + 1)
    memo[target] = min_count
    return min_count

最后直接返回dfs(n)即可，不用再取长度。

3. 递归DFS的栈溢出风险与性能问题 #

Python递归深度有限，大n可能触发栈溢出。更高效的是用动态规划（DP）迭代或广度优先搜索（BFS）：

方案一：动态规划

DP数组dp[i]表示和为i的最少完全平方数数量，初始化dp[0]=0，其他为无穷大，遍历更新数组：

class Solution:
    def numSquares(self, n: int) -> int:
        # 生成完全平方数列表
        nums = []
        i = 1
        while i*i <= n:
            nums.append(i*i)
            i += 1
        
        dp = [float('inf')] * (n + 1)
        dp[0] = 0
        
        for num in nums:
            for j in range(num, n + 1):
                dp[j] = min(dp[j], dp[j - num] + 1)
        
        return dp[n]

方案二：广度优先搜索（BFS）

BFS的层级对应使用的完全平方数数量，第一次到达n时的层级就是答案，效率更高：

class Solution:
    def numSquares(self, n: int) -> int:
        # 生成完全平方数列表
        nums = []
        i = 1
        while i*i <= n:
            nums.append(i*i)
            i += 1
        
        from collections import deque
        visited = set()
        q = deque()
        q.append((n, 0))
        visited.add(n)
        
        while q:
            current, count = q.popleft()
            if current == 0:
                return count
            for num in nums:
                next_val = current - num
                if next_val >= 0 and next_val not in visited:
                    visited.add(next_val)
                    q.append((next_val, count + 1))

最终优化效果 #

以上优化后，处理8328这类大输入时，DP和BFS都能快速得到结果，不会超时。

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