LC 279. 完全平方数

题目描述

这是 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$

完全背包（朴素解法）

首先「完全平方数」有无限个，但要凑成的数字是给定的。

因此第一步可以将范围在 $[1, n]$ 内的「完全平方数」预处理出来。

这一步其实就是把所有可能用到的「物品」预处理出来。

从而将问题转换为：给定了若干个数字，每个数字可以被使用无限次，求凑出目标值 $n$ 所需要用到的是最少数字个数是多少。

由于题目没有限制我们相同的「完全平方数」只能使用一次，属于「完全背包」模型。

目前我们学过的两类背包问题（01 背包 & 完全背包）的原始状态定义都是两维：

  • 第一维 $i$ 代表物品编号

  • 第二维 $j$ 代表容量

其中第二维 $j$ 又有「不超过容量 $j$」和「容量恰好为 $j$」两种定义，本题要我们求「恰好」凑出 $n$ 所需要的最少个数。

因此我们可以调整我们的「状态定义」：

$f[i][j]$ 为考虑前 $i$ 个数字，凑出数字总和 $j$ 所需要用到的最少数字数量。

不失一般性的分析 $f[i][j]$，对于第 $i$ 个数字（假设数值为 $t$），我们有如下选择：

  • 选 $0$ 个数字 $i$，此时有 $f[i][j] = f[i - 1][j]$
  • 选 $1$ 个数字 $i$，此时有 $f[i][j] = f[i - 1][j - t] + 1$
  • 选 $2$ 个数字 $i$，此时有 $f[i][j] = f[i - 1][j - 2 * t] + 2$
    …
  • 选 $k$ 个数字 $i$，此时有 $f[i][j] = f[i - 1][j - k * t] + k$

因此我们的状态转移方程为：

当然，能够选择 $k$ 个数字 $i$ 的前提是，剩余的数字 $j - k t$ 也能够被其他「完全平方数」凑出，即 $f[i - 1][j - k t]$ 为有意义的值。

代码（朴素完全背包问题的复杂度是 $O(n^2 * \sqrt{n})$ 的，有超时风险，让物品下标从 $0$ 开始，单独处理第一个物品的 $P2$ 代码勉强能过）：

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
33
34
35
36
37
class Solution {
    int INF = 0x3f3f3f3f;
    public int numSquares(int n) {
        // 预处理出所有可能用到的「完全平方数」
        List<Integer> list = new ArrayList<>();
        int t = 1;
        while (t * t <= n) {
            list.add(t * t);
            t++;
        }

        // f[i][j] 代表考虑前 i 个物品，凑出 j 所使用到的最小元素个数
        int m = list.size();
        int[][] f = new int[m + 1][n + 1]; 
        
        // 当没有任何数时，除了 f[0][0] 为 0（花费 0 个数值凑出 0），其他均为无效值
        Arrays.fill(f[0], INF);
        f[0][0] = 0; 

        // 处理剩余数的情况
        for (int i = 1; i <= m ; i++) {
            int x = list.get(i - 1);
            for (int j = 0; j <= n; j++) {
                // 对于不选第 i 个数的情况
                f[i][j] = f[i - 1][j];
                // 对于选 k 次第 i 个数的情况
                for (int k = 1; k * x <= j; k++) {
                    // 能够选择 k 个 x 的前提是剩余的数字 j - k * x 也能被凑出
                    if (f[i - 1][j - k * x] != INF) {
                        f[i][j] = Math.min(f[i][j], f[i - 1][j - k * x] + k);
                    }
                }
            }
        }
        return f[m][n];
    }
}

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
    int INF = -1;
    public int numSquares(int n) {
        // 预处理出所有可能用到的「完全平方数」
        List<Integer> list = new ArrayList<>();
        int idx = 1;
        while (idx * idx <= n) {
            list.add(idx * idx);
            idx++;
        }

        // f[i][j] 代表考虑前 i 个物品，凑出 j 所使用到的最小元素个数
        int len = list.size();
        int[][] f = new int[len][n + 1]; 
        
        // 处理第一个数的情况
        for (int j = 0; j <= n; j++) {
            int t = list.get(0);
            int k = j / t;
            if (k * t == j) { // 只有容量为第一个数的整数倍的才能凑出
                f[0][j] = k; 
            } else { // 其余则为无效值
                f[0][j] = INF;
            }
        }

        // 处理剩余数的情况
        for (int i = 1; i < len; i++) {
            int t = list.get(i);
            for (int j = 0; j <= n; j++) {
                // 对于不选第 i 个数的情况
                f[i][j] = f[i - 1][j];
                // 对于选 k 次第 i 个数的情况
                for (int k = 1; k * t <= j; k++) {
                    // 能够选择 k 个 t 的前提是剩余的数字 j - k * t 也能被凑出
                    // 使用 0x3f3f3f3f 作为最大值（预留累加空间）可以省去该判断
                    if (f[i - 1][j - k * t] != INF) {
                        f[i][j] = Math.min(f[i][j], f[i - 1][j - k * t] + k);
                    }
                }
                
            }
        }
        return f[len - 1][n];
    }
}

  • 时间复杂度：预处理出所有可能用到的数字复杂度为 $O(\sqrt{n})$，共有 $n \sqrt{n}$ 个状态需要转移，每个状态转移最多遍历 $n$ 次，因此转移完所有状态复杂度为 $O(n^2 \sqrt{n})$。整体复杂度为 $O(n^2 * \sqrt{n})$。
  • 空间复杂度：$O(n * \sqrt{n})$。

完全背包（进阶）

显然朴素版的完全背包进行求解复杂度有点高。

这次我们还是按照同样的思路再进行一次推导，加强对这种「一维空间优化」方式的理解。

从二维的状态转移方程入手进行分析（假设第 $i$ 个数字为 $t$）：

640.png

至此，我们得到了最终的状态转移方程：

同时，预处理「物品」的逻辑也能直接下放到转移过程去做。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int numSquares(int n) {
        int[] f = new int[n + 1];
        Arrays.fill(f, 0x3f3f3f3f);
        f[0] = 0;
        for (int t = 1; t * t <= n; t++) {
            int x = t * t;
            for (int j = x; j <= n; j++) {
                f[j] = Math.min(f[j], f[j - x] + 1);
            }
        }
        return f[n];
    }
}

  • 时间复杂度：共有 $n \sqrt{n}$ 个状态需要转移，复杂度为 $O(n \sqrt{n})$。
  • 空间复杂度：$O(n)$。

最后

这是我们「刷穿 LeetCode」系列文章的第 No.279 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。