279. Perfect Squares（Medium)

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

Example:

Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.

方法一：回溯法DFS暴力搜索 超时

    def numSquares(self, n):
        m = int(n ** 0.5)
        L = []
        for i in range(1,m+1):
            L.append(i**2)
        res = []
        self.dfs(L, n, res, [])
        return min([len(res[i]) for i in range(len(res))])
        
    def dfs(self, L, n, res, tmp):
        if n == 0:
            res.append(tmp)
        else:
            for i in range(len(L)-1,-1,-1):
                if L[i] <= n:
                    self.dfs(L, n - L[i], res, tmp + [L[i]])

方法二：BFS AC 304 ms

该题可以看作是搜索树的最小深度，因此只要BFS找到的第一个解一定是深度最小的

    def numSquares(self, n):
        q = [(n, 0)]
        visited = [False for _ in range(n + 1)]
        visited[n] = True
        while q:
            num, step = q.pop(0)   
            i = 1
            rest_num = num - i ** 2
            while rest_num >= 0:            
                if rest_num == 0: 
                    return step + 1   # 树形结构，最先到达0的一定是步数最少的
                if not visited[rest_num]:
                    q.append((rest_num, step + 1))
                    visited[rest_num] = True     #减枝
                i += 1
                rest_num = num - i ** 2

方法三：DP AC 3728 ms

这题用动态规划思路写起来最简单，属于完全背包问题，每个数可以重复取或不取。

    def numSquares(self, n):
        dp = [i for i in range(n+1)]
        sqrt = int(n ** 0.5)
        for i in range(1,sqrt+1):
            for j in range(i*i, n+1):
                dp[j] = min(dp[j], dp[j-i*i]+1)
        return dp[-1]

方法四：数学法 AC 24 ms

四平方定理： 任何一个正整数都可以表示成不超过四个整数的平方之和。
若一个数由4个整数的平方之和，则满足 n = 4^a(8b + 7)。
此外2，1可以由 n = a^2 + b^2算出。剩下的就是3个数的情况了。

    def numSquares(self, n):
        while n % 4 == 0:
            n /= 4
        if n % 8 == 7:
            return 4
        a = 0
        while a <= int(n ** 0.5):
            b = int((n - a*a) ** 0.5)
            if a*a + b*b == n:
                if a != 0 and b != 0:
                    return 2
                else:
                    return 1
            a += 1
        return 3