LeetCode-279 完全平方数

题目描述

给你一个整数 $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 \leq n \leq 10 ^ 4$

动态规划

完全背包

题目的含义可以转换为完全背包，物品的容量和代价分别是：

  • 给定 $1 \sim N$ 范围内的所有平方数，每个物品（平方数）的容量是这个平方数的值，代价是 $1$

问题转换为：求由这些平方数可以选择任意多个，组成背包容量为 $N$ 的代价的最小值

那么这个问题就是完全背包问题，我们知道完全背包问题的状态转移方程为：

  • $w[i]$ 为第 $i$ 个平方数的值
  • $1$ 表示当前物品（平方数）的代价为 $1$

$$
f[j] = min(f[j], f[j - w[i]] + 1)
$$

由于我们需要求解最小值，因此初始化：

  • $f$ 数组初始化为：$+ \infty$
  • $f[0] = 0$：放入背包容量为 $0$ 的背包，无需装入任何物品，因此代价为 $0$

时间复杂度

  • 由于 $N = 10 ^ 4$，因此这个范围内的平方数的个数就是：$\sqrt{N}$
  • 背包容量为：$N$

因此整体时间复杂度为：$O(N * \sqrt{N}) \approx 10 ^ 6$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int numSquares(int n) {
        vector<int> vec;
        // 将所有的 1 ~ n 之间的所有平方数处理出来
        for (int i = 1; i <= n / i; ++i) vec.push_back(i * i);
        // 完全背包状态方程，初始化
        vector<int> f(n + 1, 1e9);
        f[0] = 0;
        // 枚举每一个物品，相当于枚举每一个物品
        for (int i = 0; i < vec.size(); ++i) {
            // 每个物品的容量就是：平方数的值，代价是 1
            int w = vec[i];
            for (int j = w; j <= n; ++j) {
                f[j] = min(f[j], f[j - w] + 1);
            }
        }
        return f[n];
    }
};

数学

四平方和定理

这个是需要知道这个结论的，不是很普遍：

四平方和定理：

任意一个正整数都可以被表示为至多四个正整数的平方和。

同时具有以下性质：

  • 如果 $n = 4 ^ k * (8 * m + 7), k, m \in Z$，那么 只能表示 成 四个正整数 的平方和（这里式子的含义是 $n$ 可以表示成后面的形式）

因此，我们根据上面的定理可以知道：**答案一定只能是：$1, 2, 3, 4$**：

  • 答案是 $1$：只有 $n$ 是平方数的时候，符合
  • 答案是 $2$：也就是：$n = a ^ 2 + b ^ 2$，那么可以枚举：$a ^ 2$，判定 $n - a ^ 2$ 是否是平方数即可
  • 答案是 $4$：$n$ 可以表示成：$n = 4 ^ k * (8 * m + 7), k, m \in Z$，也就是将 $n$ 中 $4$ 全部除掉后，判定取模 $8$ 的结果是否为 $7$ 即可
  • 答案是 $3$：不是上面的三种情况下，答案只能是 $3$

注意：题目要求解的最小的表示数量，因为四平方和定理可以知道如果 $n$ 符合 $n = 4 ^ k * (8 * m + 7), k, m \in Z$ 的话，那么就 只能 表示成 $4$ 个整数，因此可以先判定 $4$ 是否可以表示，如果不能表示的话，结果就是 $3$。也就是说：不存在同时可以表示 $3, 4$ 的情况。

时间复杂度

  • 当答案可能是 $2$ 的时候，需要枚举 $a ^ 2$，因此枚举复杂度为：$O(\sqrt{N})$

因此整体时间复杂度为：$O(\sqrt{N})$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool check(int n) {
        int sqrtn = (int)sqrt(n);
        return sqrtn * sqrtn == n;
    }

    bool check4(int n) {
        while (n % 4 == 0) n /= 4;
        return n % 8 == 7;
    }

    int numSquares(int n) {
        if (check(n)) return 1;
        else {
            for (int i = 1; i <= n / i; ++i) {
                if (check(n - i * i)) return 2;
            }
            if (check4(n)) return 4;
            return 3;
        }
    }
};