📝 题目描述

题目链接：完全平方数

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

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

示例：

1
2
3
4
5
6
7
8
9
10
11
示例 1：

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

示例 2：

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

提示：

  • 1 <= n <= 10^4

💡 解题思路

方法一：动态规划

我们可以依据题目的要求写出状态表达式：f[i]f[i] 表示最少需要多少个数的平方来表示整数 ii。

这些数必然落在区间 [1,i][1,\sqrt{i}]。我们可以枚举这些数，假设当前枚举到 jj，那么我们还需要取若干数的平方，构成 i−j2i−j^2。此时我们发现该子问题和原问题类似，只是规模变小了。这符合了动态规划的要求，于是我们可以写出状态转移方程。

f[i]=1+j=min⁡j=1⌊i⌋f[i−j2]f[i]=1+j=\min_{j = 1}^{⌊\sqrt{i}⌋} f[i−j^2]

其中 f[0]=0f[0]=0 为边界条件，实际上我们无法表示数字 00，只是为了保证状态转移过程中遇到 jj 恰为 ii
​ 的情况合法。

同时因为计算 f[i]f[i] 时所需要用到的状态仅有 f[i−j2]f[i−j^2]，必然小于 ii，因此我们只需要从小到大地枚举 ii 来计算 f[i]f[i] 即可。

方法二：数学

一个数学定理可以帮助解决本题：“四平方和定理”。

四平方和定理证明了任意一个正整数都可以被表示为至多四个正整数的平方和。这给出了本题的答案的上界。

同时四平方和定理包含了一个更强的结论：当且仅当 n≠4k×(8m+7)n \neq 4^k×(8m+7) 时，nn 可以被表示为至多三个正整数的平方和。因此，当 n=4k×(8m+7)n=4^k×(8m+7) 时，nn 只能被表示为四个正整数的平方和。此时我们可以直接返回 44。

当 n≠4k×(8m+7)n \neq 4^k×(8m+7) 时，我们需要判断到底多少个完全平方数能够表示 nn，我们知道答案只会是 1,2,31,2,3 中的一个：

  • 答案为 11 时，则必有 nn 为完全平方数，这很好判断；
  • 答案为 22 时，则有 n=a2+b2n=a^2+b^2，我们只需要枚举所有的 a(1≤a≤n)a(1≤a≤\sqrt{n})，判断 n−a2n−a^2 是否为完全平方数即可；
  • 答案为 33 时，我们很难在一个优秀的时间复杂度内解决它，但我们只需要检查答案为 11 或 22 的两种情况，即可利用排除法确定答案。

🔧 代码实现

1、动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int numSquares(int n) {
        vector<int> f(n + 1, 0);
        for (int i = 1; i <= n; i++) {
            int minn = INT_MAX;
            for (int j = 1; j * j <= i; j++) {
                minn = min(minn, f[i - j * j]);
            }
            f[i] = minn + 1;
        }
        return f[n];
    }
};

2、优化解法

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; i++) {
            int j = n - i * i;
            if (isPerfectSquare(j)) {
                return 2;
            }
        }
        return 3;
    }
};

📊 复杂度分析

1、动态规划

  • 时间复杂度：O(nn)O(n\sqrt{n})，其中 nn 为给定的正整数。状态转移方程的时间复杂度为 O(n)O(\sqrt{n})，共需要计算 nn 个状态。
  • 空间复杂度：O(n)O(n)。我们需要 O(n)O(n) 的空间保存状态。

2、数学

  • 时间复杂度：O(n)O(\sqrt{n})，其中 nn 为给定的正整数。最坏情况下答案为 33，我们需要运行所有的判断，而判断答案是否为 11 的时间复杂度为 O(1)O(1)，判断答案是否为 44 的时间复杂度为 O(logn)O(logn)，剩余判断为 O(n)O(n)，因此总时间复杂度为 O(logn+n)=O(n)O(logn+\sqrt{n})=O(n)。
  • 空间复杂度：O(1)O(1)。我们只需要常数的空间保存若干变量。

🎯 总结

  • 核心思想：想出使用 j×j<=ij \times j <= i 来表示范围。