题目描述

给定正整数 n，找到若干个完全平方数(比如 1, 4, 9, 16, ...) 使得他们的和等于 n。你需要让平方数的个数最少。

比如 n = 12，返回 3 ，因为 12 = 4 + 4 + 4 ；给定 n = 13，返回 2 ，因为 13 = 4 + 9。

我的解法——DP（TLE）

采用动态规划实现。用 dp[i] 数组存储第 i 个数的完美平方数。递推式为：dp[i] = Math.max(dp[j] + dp[i-j], dp[i]，认为 i 的完全平方数是从和为 i 的两个完全平方数 dp[j] 和 dp[i-j]之和，然后从中取最小。
复杂度O(n2)

class Solution:
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        
        dp = [0] * (n + 1)
        dp[1] = 1
        
        for i in range(2,n + 1):
            s = int(pow(i,0.5))
            if(s * s == i):
                dp[i] = 1
            else:
                min_now = dp[1] + dp[i - 1]
                for j in range(2,int((i + 1) / 2) + 1):
                    now = dp[j] + dp[i - j]
                    if(now < min_now):
                        min_now = now
                dp[i] = min_now
        
        return dp[n]

最优解法——DP（AC）

所有的完美平方数都可以看做一个普通数加上一个完美平方数，那么递推式就变为了：dp[i + j * j] = Math.min(dp[i] + 1, dp[i + j * j])
复杂度：O(n2)
Beat 14.29%

class Solution:
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        
        dp = [n] * (n + 1)
        
        
        for i in range(n + 1):
            if(pow(int(pow(i,0.5)),2) == i):
                dp[i] = 1
        for i in range(1,n + 1):
            j = 1
            while(i + j * j <= n):  # 这里复杂度小了,内层循环只要满足i^2<=n即可
                dp[i + j * j] = min(dp[i] + 1,dp[i + j * j])
                j += 1
        return dp[n]

其他解法——图论

见https://blog.csdn.net/dst111188/article/details/69950493

其他解法——数论

四平方和定理(Lagrange’s Four-Square Theorem)：所有自然数至多只要用四个数的平方和就可以表示。
见http://bookshadow.com/weblog/2015/09/09/leetcode-perfect-squares/