完全平方数 - Stellar Observer Protocol

828 字

4 分钟

完全平方数

2025-08-11

Algorithms

广度优先搜索

/

数学

/

动态规划

题目描述#

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

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

解题思路#

动态规划：
- 定义 dp[i] 表示和为 i 的最少完全平方数个数
- 初始化 dp = 0（边界条件）
- 状态转移：dp[i] = min(dp[i], dp[i - j*j] + 1) （j 为平方数，1 ≤ j ≤ √i）
数学优化：
- 基于四平方和定理：任何正整数可表示为4个平方数和
- 特殊处理：若 n 是完全平方数，直接返回1
BFS剪枝：
- 将问题转化为层级遍历（0→n的最短路径）
- 每层减去平方数，首次到达0的层级即解

关键洞察#

子问题重叠：
- 大数解依赖小数解（如 dp=dp+1=dp+3）
- 动态规划自然复用子问题解
平方数边界：
- 只需考虑 j*j ≤ i 的平方数
- 内层循环可优化为 j=1→√i
四平方和定理：
- 解仅可能为1/2/3/4四种情况
- 若 n=4^k*(8m+7) 则解为4
BFS层级特性：
- 每层表示当前剩余数值
- 减平方数操作等价于边权为1的图搜索

复杂度分析#

方法	时间复杂度	空间复杂度
动态规划	O(n√n)	O(n)
BFS	O(n)（最坏情况）	O(n)
数学法	O(√n)	O(1)

注：n为输入正整数，√n表示平方根取整

代码实现#

动态规划

1
var numSquares = function (n) {
2
    // 创建动态规划数组，dp[i] 表示和为 i 的最少完全平方数数量
3
    const dp = new Array(n + 1).fill(Infinity);
4
    dp[0] = 0; // 基础情况：和为 0 需要 0 个平方数
5
    // 预先计算所有可能用到的平方数
6
    const squares = [];
7
    for (let i = 1; i * i <= n; i++) {
8
        squares.push(i * i);
9
    }
10
    // 动态规划填充过程
11
    for (let i = 1; i <= n; i++) {
12
        for (const square of squares) {
13
            if (square > i) break; // 平方数大于当前值，提前终止
14
            dp[i] = Math.min(dp[i], dp[i - square] + 1);
15
        }
16
    }
17
    return dp[n];
18
};

BFS

1
/**
2
 * @param {number} n
3
 * @return {number}
4
 */
5
const numSquares = (n) => {
6
    const queue = [n];
7
    const visited = new Set([n]);
8
    let level = 0;
9

10
    while (queue.length) {
11
        level++;
12
        const size = queue.length;
13
        for (let i = 0; i < size; i++) {
14
            const cur = queue.shift();
15
            for (let j = 1; j * j <= cur; j++) {
16
                const next = cur - j * j;
17
                if (next === 0) return level;
18
                if (!visited.has(next)) {
19
                    visited.add(next);
20
                    queue.push(next);
21
                }
22
            }
23
        }
24
    }
25
    return level;
26
};

数学法

1
/**
2
 * @param {number} n
3
 * @return {number}
4
 */
5
const numSquares = (n) => {
6
    // 检测是否为完全平方数
7
    const isSquare = (x) => Math.floor(Math.sqrt(x)) ** 2 === x;
8

9
    // 情况1：n为完全平方数
10
    if (isSquare(n)) return 1;
11

12
    // 情况2：检查是否存在 a^2+b^2=n
13
    for (let i = 1; i * i <= n; i++) {
14
        if (isSquare(n - i * i)) return 2;
15
    }
16

17
    // 情况3：四平方和定理特殊情况
18
    while (n % 4 === 0) n /= 4;
19
    if (n % 8 === 7) return 4;
20

21
    // 其他情况为3
22
    return 3;
23
};