LeetCode 279. 完全平方数

Categories:

题目描述
思路分析
1. 解法一：动态规划（完全背包）（推荐）
2. 解法二：BFS（最短路径）
相似题目

题目描述

✅ 279. 完全平方数

思路分析

解法一：动态规划（完全背包）（推荐）

核心思路：

将完全平方数（1、4、9、16…）看作”硬币面值”，n 看作”总金额”，问题转化为：用最少枚硬币凑出金额 n，与 322. 零钱兑换结构完全相同。

定义 dp[i] 为凑出整数 i 所需的最少完全平方数个数。

状态转移：枚举所有满足 j² ≤ i 的完全平方数，取最小值：dp[i] = min(dp[i - j²] + 1)，其中 j = 1, 2, ..., √i。

初始值：dp[0] = 0（凑出 0 不需要任何数），其余初始化为 Integer.MAX_VALUE。

完全背包特征：每个平方数可以重复使用，外层枚举目标值 i，内层枚举平方数 j²，顺序遍历（区别于 0-1 背包的逆序）。

复杂度分析：

时间复杂度：O(n√n)，其中 n 为目标整数，外层枚举 n 个目标值，内层枚举 √i 个平方数

空间复杂度：O(n)，其中 n 为目标整数，使用一维 dp 数组

class Solution {
    public int numSquares(int n) {
        // dp[i] 表示凑出整数 i 所需的最少完全平方数个数
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        // 凑出 0 不需要任何数
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            // 枚举所有满足 j² <= i 的完全平方数
            for (int j = 1; j * j <= i; j++) {
                // 状态转移：选当前平方数 j²，从 dp[i - j*j] 转移而来
                if (dp[i - j * j] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
                }
            }
        }
        return dp[n];
    }
}

func numSquares(n int) int {
    // dp[i] 表示凑出整数 i 所需的最少完全平方数个数
    dp := make([]int, n+1)
    for i := 1; i <= n; i++ {
        dp[i] = math.MaxInt32
    }
    // 凑出 0 不需要任何数
    dp[0] = 0

    for i := 1; i <= n; i++ {
        // 枚举所有满足 j² <= i 的完全平方数
        for j := 1; j*j <= i; j++ {
            // 状态转移：选当前平方数 j²，从 dp[i-j*j] 转移而来
            if dp[i-j*j] != math.MaxInt32 {
                dp[i] = min(dp[i], dp[i-j*j]+1)
            }
        }
    }

    return dp[n]
}

解法二：BFS（最短路径）

核心思路：

将整数 n 看作图中的起点，每次减去一个完全平方数到达新节点，问题转化为求从 n 到 0 的最短路径长度。

BFS 按层遍历，第一次到达 0 时所经过的层数即为答案（每层代表使用了一个完全平方数）。

使用 visited 数组避免重复访问同一节点，防止死循环并提升效率。

复杂度分析：

时间复杂度：O(n√n)，其中 n 为目标整数，最坏情况下每个节点需枚举 √n 个平方数

空间复杂度：O(n)，其中 n 为目标整数，队列和 visited 数组最多存储 n 个节点

class Solution {
    public int numSquares(int n) {
        // 使用 BFS 求从 n 到 0 的最短路径
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[n + 1];
        queue.offer(n);
        visited[n] = true;
        int level = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            level++;
            for (int i = 0; i < size; i++) {
                int cur = queue.poll();
                // 枚举所有满足 j² <= cur 的完全平方数
                for (int j = 1; j * j <= cur; j++) {
                    int next = cur - j * j;
                    // 到达 0 即为找到最短路径
                    if (next == 0) {
                        return level;
                    }
                    if (!visited[next]) {
                        visited[next] = true;
                        queue.offer(next);
                    }
                }
            }
        }

        return level;
    }
}

func numSquares(n int) int {
    // 使用 BFS 求从 n 到 0 的最短路径
    queue := []int{n}
    visited := make([]bool, n+1)
    visited[n] = true
    level := 0

    for len(queue) > 0 {
        size := len(queue)
        level++
        for i := 0; i < size; i++ {
            cur := queue[i]
            // 枚举所有满足 j² <= cur 的完全平方数
            for j := 1; j*j <= cur; j++ {
                next := cur - j*j
                // 到达 0 即为找到最短路径
                if next == 0 {
                    return level
                }
                if !visited[next] {
                    visited[next] = true
                    queue = append(queue, next)
                }
            }
        }
        queue = queue[size:]
    }

    return level
}

相似题目

题目	难度	考察点
322. 零钱兑换	中等	完全背包求最少硬币数
518. 零钱兑换 II	中等	完全背包求方案数
139. 单词拆分	中等	完全背包 / DP
343. 整数拆分	中等	数学 + DP
368. 最大整除子集	中等	动态规划
127. 单词接龙	困难	BFS 最短路（同 BFS 解法思路）

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/70176092