求和为 n 的最小完全平方数

Question

我正在尝试解决找到最小数量的完美平方（即1、2、4、9..）的问题，其总和为n

这是我的自上而下的递归方法：

import math

class Solution:
    def numSquares(self, n: int) -> int:
        
        dp = [math.inf] * (n + 1)
        dp[0] = 0
        dp[1] = 1 

        def solve(n: int):
            if dp[n] != math.inf:
                return dp[n]

            for i in range(n, 0, -1):
                if n - i * i >= 0:
                    sol = solve(n - i*i)
                    dp[i] = min(1 + sol, dp[i])

            return dp[n]

        solve(n)
        print(dp)

Solution().numSquares(12)

我无法弄清楚为什么这段代码不能产生正确的结果。你能帮我找到这个错误吗？

谢谢！

Answer 1

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [math.inf] * (n + 1)
        dp[0] = 0
        dp[1] = 1
        
        def solve(n: int):
            if dp[n] != math.inf:
                return dp[n]
            sol = math.inf
            for i in range(n, 0, -1):
                if n - i * i >= 0:
                    sol = min(sol, solve(n-i*i))
            dp[n] = sol+1
            
            return dp[n]
        
        return solve(n)

上面是您的解决方案的更正版本，但它仍然太慢，因为您检查每个数字，即使它们的平方明显大于n。以下是通过 LC 时间限制的优化版本：

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [math.inf] * (n + 1)
        dp[0] = 0
        dp[1] = 1
        
        def solve(n: int):
            if dp[n] != math.inf:
                return dp[n]
            sol = math.inf
            for i in range(1, n):
                if n - i * i >= 0:
                    sol = min(sol, solve(n-i*i))
                else:
                    break
            dp[n] = sol+1
            
            return dp[n]
        
        return solve(n)

但仍有优化的空间。一点点：

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [math.inf] * (n + 1)
        dp[0] = 0
        dp[1] = 1
        
        def solve(n: int):
            if dp[n] != math.inf:
                return dp[n]
            sol = math.inf
            for i in range(1, math.floor(n**(1/2))+1):
                sol = min(sol, solve(n-i*i))
            dp[n] = sol+1
            
            return dp[n]
        
        return solve(n)

解决这个问题的另一种方法是使用 BFS 方法。想象一下所有到达的路径n都是一棵树，其中叶子是有价值的n，并且每次移动到相邻节点的成本都是一。在 BFS 中，第一次命中是最好的命中，因为成本都是相等的：

class Solution:
    def numSquares(self, n: int) -> int:
        deq = collections.deque([n])
        steps = 1
        
        while deq:
            n = len(deq)
            
            for _ in range(n):
                node = deq.popleft()
                for i in range(1, floor(node**(1/2))+1):
                    num = i**2
                    if num == node:
                        return steps
                    deq.append(node - num)
            steps += 1

正如德米特里·比琴科（Dmitry Bychenko）所指出的，您可以使用拉格朗日定理来解决这个问题。这是一篇关于它的很好的文章和 python 解决方案。