动态规划求解完全平方数的最小数量（LeetCode 279）

---

题目描述

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

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

示例 1:

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

示例 2:

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

提示:

• 1 <= n <= 10^4

动态规划

核心思路

动态规划的思路是创建一个数组 f，其中 f[i] 表示组成数字 i 所需的最少完全平方数的数量。初始化时，f[0] = 0（因为 0 不需要任何平方数），然后对于每个 i 从 1 到 n，我们遍历所有可能的完全平方数 j * j（其中 j 从 1 开始，直到 j * j <= i），并更新 f[i] 为 f[i - j * j] + 1 的最小值。

这种方法确保了对于每个数字 i，我们都能找到最优解。时间复杂度为 O(n * sqrt(n))，空间复杂度为 O(n)。

代码实现

public int numSquares(int n) {
    // 创建动态规划数组，f[i] 表示组成 i 所需的最少完全平方数数量
    int[] f = new int[n + 1];
    // 从 1 到 n 计算每个数字的最少平方数数量
    for (int i = 1; i <= n; i++) {
        int min = Integer.MAX_VALUE; // 初始化最小值
        // 遍历所有可能的完全平方数 j*j，其中 j*j <= i
        for (int j = 1; j * j <= i; j++) {
            // 更新最小值，f[i - j*j] 表示减去一个平方数后的最优解
            min = Math.min(min, f[i - j * j]);
        }
        // 当前 i 的最优解为 min + 1（加上当前平方数）
        f[i] = min + 1;
    }
    return f[n]; // 返回结果
}

复杂度分析

• 时间复杂度：O(n * sqrt(n))，因为对于每个数字 i，内层循环最多运行 sqrt(i) 次。
• 空间复杂度：O(n)，需要长度为 n + 1 的数组来存储状态。

数学方法（四平方和定理）

核心思路

四平方和定理指出，每个正整数都可以表示为最多四个完全平方数的和。利用这一定理，我们可以通过数学推导来减少计算：

1. 如果 n 本身是完全平方数，直接返回 1。
2. 如果 n 满足公式 n = 4^k * (8m + 7)，那么它必须由四个完全平方数组成，返回 4。
3. 检查 n 是否可以由两个完全平方数组成，即遍历 i 从 1 到 sqrt(n)，检查 n - i * i 是否为完全平方数。
4. 如果以上都不满足，则返回 3。

这种方法的时间复杂度为 O(sqrt(n))，空间复杂度为 O(1)，效率更高。

代码实现

public int numSquares(int n) {
    // 如果 n 是完全平方数，直接返回 1
    if (isPerfectSquare(n)) {
        return 1;
    }
    // 如果 n 满足 4^k*(8m+7) 的形式，返回 4
    if (checkAnswer4(n)) {
        return 4;
    }
    // 检查是否可以由两个完全平方数组成
    for (int i = 1; i * i <= n; i++) {
        int j = n - i * i;
        // 如果 j 是完全平方数，返回 2
        if (isPerfectSquare(j)) {
            return 2;
        }
    }
    // 否则返回 3
    return 3;
}

// 判断是否为完全平方数
public boolean isPerfectSquare(int x) {
    int y = (int) Math.sqrt(x);
    return y * y == x;
}

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

复杂度分析

• 时间复杂度：O(sqrt(n))，因为主要开销在检查两个平方数时循环最多 sqrt(n) 次。
• 空间复杂度：O(1)，只使用了常数级别的额外空间。

总结

动态规划方法直观易懂，适用于一般范围的 n，但当 n 较大时可能效率较低。数学方法基于四平方和定理，效率更高，适合大数情况。在实际应用中，可以根据问题规模选择合适的方法。

来源

279. 完全平方数 | 力扣（LeetCode）
279. 完全平方数 | 题解 | 力扣官方题解

---