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

Question

我正在尝试解决找到总和为 n

的最小完全平方数（即 1、2、4、9..）的问题

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

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 并且每次移动到相邻节点的成本为 1。在 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 所指出的，您可以使用拉格朗日定理解决该问题。这是关于它的nice write up and python solution。

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

Finding the minimum number of perfect squares to sum up to n

python

algorithm

recursion

dynamic-programming