Leetcode 279.完全平方数

题目描述：

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

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

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

1
2
3

输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4

示例 2：

1
2
3

输入：n = 13
输出：2
解释：13 = 4 + 9

提示：

• $1 <= n <= 10^4$

链接：

https://leetcode-cn.com/problems/perfect-squares

题目分析

1.动态规划

  看到这道题的时候，第一感觉就是动态规划，思考一下其中的过程。对于一个数 $n$，我们将其表示成一个完全平方数 $i^2$ 和另一个数的和，这个问题就转化了成了另一个更小的数 $n-i^2$ 的问题。那么我们令 $f(n)$ 是和为 $n$ 的完全平方数的最少数量，我们要找的是使得 $f(n-i^2)$ 最小的那个 $i$，则有以下动态规划转移方程 $\displaystyle f(n) = 1 + \min^{\lfloor\sqrt{n}\rfloor}_{i}(f(n-i^2))$。特别的，我们令 $f(0)=0$，这样一个完全平方数就刚好能用本身表示。而状态转移是需要用到更小的状态，则我们从小到大进行动态规划即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n+1);
        dp[0] = 0;
        for(int i = 1; i <= n; i++){
            int mindp = INT_MAX;
            for(int root = 1; root * root <= i; root++){
                mindp = min(mindp, dp[i-root*root]);
            }
            dp[i] = mindp + 1;
        }
        return dp[n];
    }
};

  时间复杂度：$O(n\sqrt{n})$，其中 $n$ 是正整数的大小。我们进行了从 1 到 $n$ 的动态规划，而每次规划需要计算 $\lfloor\sqrt{n}\rfloor$ 个状态中的最小值。
  空间复杂度：$O(n)$，其中 $n$ 是正整数的大小。也即存储动态规划状态的数组大小。

2.数学方法 - 官方题解

  做出了上面那种动态规划的方法后，总是觉得状态转移需要 $\sqrt{n}$ 个状态有点多，以为有更好的动态规划，没想到那样就是动态规划的解法了。而更好的解法是使用数学定理的，这个实在是知识盲区。
  这里使用到的数学定理是 四平方和定理。这个定理说，每个正整数均可表示为 4 个整数的平方和。也就是说，这道题的答案不会超过 4。同时四平方和定理包含了一个更强的结论：当且仅当 $n\neq4^k\times(8m+7)$ 时，$n$ 可以被表示为至多三个正整数的平方和。也就是说，当 $n=4^k\times(8m+7)$ 时，答案一定是 4。而对于剩下的数，还剩下 3 种可能。如果答案是 1，也即该数本身就是完全平方数，容易判断。如果答案是 2，则 $n$ 可以表示成两个完全平方数的和，则我们枚举不大于 $\sqrt{\frac{n}{2}}$ 的平方，并判断减去之后另一个数是不是也是完全平方数就可以了。而剩下的数答案就是 3。
  这里对官方题解做了一点点修改，官方题解枚举答案 2 的时候是枚举到了 $\sqrt{n}$，其实到了一半就可以了。并且在看官方题解的时候，注意到了求平方根函数 sqrt 的时间复杂度是 $O(1)$，有点不解，去了解了一下算法原理，看完神清气爽，不得不感叹前人的智慧。这里附上链接 sqrt方法复杂度探讨。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution {
public:
    // 判断是否为完全平方数
    bool isPerfectSquare(int x) {
        int y = sqrt(x);
        return y * y == x;
    }

    // 判断是否能表示为 4^k*(8m+7)
    bool checkAnswer4(int x) {
        while (x % 4 == 0) {
            x /= 4;
        }
        return x % 8 == 7;
    }

    int numSquares(int n) {
        if (isPerfectSquare(n)) {
            return 1;
        }
        if (checkAnswer4(n)) {
            return 4;
        }
        for (int i = 1; i * i <= n / 2; i++) {
            int j = n - i * i;
            if (isPerfectSquare(j)) {
                return 2;
            }
        }
        return 3;
    }
};

  时间复杂度：$O(\sqrt{n})$，其中 $n$ 为给定的正整数。最坏情况下答案为 3，我们需要运行所有的判断，而判断答案是否为 1 的时间复杂度为 $O(1)$，判断答案是否为 4 的时间复杂度为 $O(\log n)$，判断为 2 的时间复杂度为 $O(\sqrt{n})$。
  空间复杂度：$O(1)$。我们只需要常数的空间保存若干变量。

3.贪心法 - 官方题解评论区

  在看官方题解的评论的时候，还看到一种贪心的方法。通过上面的分析我们也知道，这道题的答案是不会超过 4 的，所以其实使用贪心的思路不会比正向动态规划慢。贪心的思路就是贪心地认为是 1 个完全平方数的和，不行再判断是不是 2 个完全平方数的和，不行再判断是不是 3 个完全平方数的和，以此类推直到找到答案。
  这样做的好处是减少了很多对结果没有用的状态，相当于从结果倒推需要的状态，类似于 DFS 的思想去搜索，在这道题应该是蛮快的。这里附上评论区大佬的 python 代码。这份代码还可以优化，p 循环不需要 ps 里面的所有数，大于 n/2 之后就可以停止了。

1
2
3
4
5
6
7
8
9
10
11

ps = set([i * i for i in range(1, int(n**0.5)+1)])
def divisible(n, count):
    if count == 1: return n in ps
    for p in ps:
        if divisible(n-p, count-1):
            return True
    return False

for count in range(1, n+1):
    if divisible(n, count):
        return count