题目描述

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

样例

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

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

算法1

(动态规划) $O(n \sqrt n)$

1. 设 $f(i)$ 表示通过平方数组成 $i$ 所需要完全平方数的最少数量。
2. 初始时，$f(0) = 0$，其余待定。
3. 转移时，对于一个 $i$，枚举 $j$，$f(i) = \min (f(i - j * j) + 1)$，其中 $1 \le j \le \sqrt i$。
4. 最终答案为 $f(n)$。

时间复杂度

• 实际复杂度为 $S = \sum_{i=1}^n \sqrt i$，通过积分近似上界，得到 $S = O(n \sqrt n)$。

空间复杂度

• 需要额外 $O(n)$ 的空间存储状态。

C++ 代码

class Solution {
public:
    int numSquares(int n) {
        vector<int> f(n + 1, n);
        f[0] = 0;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j * j <= i; j++)
                f[i] = min(f[i], f[i - j * j] + 1);

        return f[n];
    }
};

算法2

(宽度优先搜索) $O(n \sqrt n)$

1. 通过宽搜来优化动态规划的效率，可以将整个过程看做一张图，每个数字都是一个点，两个数字之间差距为平方数时有一条单向边。
2. 使用宽搜来求从 0 到 n 的最短路。

时间复杂度

• 宽搜的时间复杂度为 $O(n + m)$，这里的点数，也就是数字个数 $n$，边数同算法 1 中的分析是 $O(\sqrt i)$。
• 故总时间复杂度仍然是 $O(n \sqrt n)$，但由于宽搜可能能快速找到到结点 $n$ 的路径，常数会比较优。

空间复杂度

• 需要额外 $O(n)$ 的空间存储队列和距离数组。

C++ 代码

class Solution {
public:
    int numSquares(int n) {
        vector<int> f(n + 1, n);
        queue<int> q;
        f[0] = 0;
        q.push(0);
        while (!q.empty()) {
            int s = q.front();
            if (s == n)
                break;
            q.pop();
            for (int i = 1; s + i * i <= n; i++)
                if (f[s + i * i] > f[s] + 1) {
                    f[s + i * i] = f[s] + 1;
                    q.push(s + i * i);
                }
        }
        return f[n];
    }
};

算法3

(数学) $O(\sqrt n + \log n)$

1. 根据 拉格朗日四平方和定理，可以得知答案必定为 1, 2, 3, 4 中的一个。
2. 其次根据 勒让德三平方和定理，可以得知当 $n = 4^a(8b+7)$时，$n$ 不能写成 3 个数的平方和。
3. 然后可以根据以上定理和枚举，判断出答案是否为 1, 2, 3，若都不是则答案为 4。

时间复杂度

• 判断平方数的时间复杂度为 $O(1)，枚举答案为 klzzwxh:0006 的时间复杂度为$O(\sqrt n)$，判断答案是否为 klzzwxh:0007 的时间复杂度为 $O(\log n)$，故总时间复杂度为 $O(\sqrt n + \log n)$。

C++ 代码

class Solution {
public:
    int numSquares(int n) {
        if ((int)sqrt(n) * (int)sqrt(n) == n)
            return 1;
        int t = n;
        while ((t & 3) == 0) t >>= 2;
        if (((t - 7) & 7) == 0)
            return 4;

        for (int i = 1; i * i <= n; i++)
            if ((int)(sqrt(n - i * i)) * (int)(sqrt(n - i * i)) == n - i * i)
                return 2;

        return 3;
    }
};