279 完全平方数

一、题目

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

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

二、题解

方法一：动态规划

思路：动态规划。

1. 核心思路

这道题要求：组成 n 的完全平方数的最少数量。

可以把问题拆成子问题：

  • 要凑出 i；
  • 最后一次可以选择一个完全平方数 j * j；
  • 那么前面就需要凑出 i - j * j。

因此可以定义：

dp[i]

表示：凑成整数 i 所需要的完全平方数的最少数量。

如果最后选择了一个完全平方数 j * j，那么状态转移为：

dp[i] = Math.min(dp[i], dp[i - j * j] + 1);

其中：

  • dp[i - j * j] 表示凑出剩余部分需要的最少数量；
  • + 1 表示当前使用了一个完全平方数 j * j。

2. 具体步骤

  1. 定义数组 dp，其中 dp[i] 表示凑成 i 的最少完全平方数数量。
  2. 初始化 dp[0] = 0，表示凑成 0 不需要任何数。
  3. 其他位置初始化为一个较大的值。
  4. 枚举每个整数 i，范围是 1 ~ n。
  5. 对于每个 i，枚举所有满足 j * j <= i 的完全平方数。
  6. 使用状态转移公式更新 dp[i]。
  7. 最后返回 dp[n]。

3. 关键逻辑

for (int j = 1; j * j <= i; j++) {
    dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
}

解释：

  • 如果选择完全平方数 j * j；
  • 那么还需要凑出 i - j * j；
  • dp[i - j * j] + 1 就是一种凑出 i 的方案；
  • 在所有方案中取最小值，就是 dp[i] 的答案。

4. 代码

import java.util.Arrays;

class Solution {
    public int numSquares(int n) {
        // 1. 定义 dp 数组
        // dp[i] 表示凑成 i 所需要的最少完全平方数数量
        int[] dp = new int[n + 1];

        // 2. 初始化为较大值
        Arrays.fill(dp, Integer.MAX_VALUE);

        // 3. 凑成 0 不需要任何数
        dp[0] = 0;

        // 4. 枚举每一个数字 i
        for (int i = 1; i <= n; i++) {
            // 枚举所有小于等于 i 的完全平方数 j * j
            for (int j = 1; j * j <= i; j++) {
                // 如果最后选择 j * j
                // 那么前面需要凑出 i - j * j
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }

        // 5. 返回凑成 n 的最少数量
        return dp[n];
    }
}

5. 复杂度分析

时间复杂度：O(nn)O(n \sqrt n)

说明：外层循环遍历 1 ~ n，内层循环枚举不超过 sqrt(n) 个完全平方数。

空间复杂度：O(n)O(n)

说明：使用了长度为 n + 1 的 dp 数组。

方法二：BFS

思路：BFS。

1. 核心思路

也可以把这道题看成一个最短路径问题。

从 n 开始，每次减去一个完全平方数。

例如：

n = 12

第一层：
12 - 1 = 11
12 - 4 = 8
12 - 9 = 3

第二层：
继续从 11、8、3 往下减完全平方数

第三层：
如果某个数减完之后变成 0，说明找到了答案

BFS 的特点是按层搜索。

因此：

  • 第 1 层表示用了 1 个完全平方数；
  • 第 2 层表示用了 2 个完全平方数；
  • 第 3 层表示用了 3 个完全平方数；
  • 第一次到达 0 时，层数就是最少数量。

2. 具体步骤

  1. 创建队列 queue，从 n 开始搜索。
  2. 使用 visited 数组记录某个数字是否已经访问过，避免重复搜索。
  3. 每一轮 BFS 表示多使用一个完全平方数。
  4. 对当前层的所有数字，尝试减去所有可能的完全平方数。
  5. 如果减完之后得到 0，直接返回当前层数。
  6. 如果不是 0，并且没有访问过，则加入队列继续搜索。

3. 关键逻辑

int next = cur - j * j;

if (next == 0) {
    return step;
}

if (!visited[next]) {
    visited[next] = true;
    queue.offer(next);
}

解释：

  • next 表示当前数字减去一个完全平方数之后的结果；
  • 如果 next == 0，说明已经成功凑出了 n；
  • 因为 BFS 是按层搜索，所以第一次到达 0 时一定是最少数量；
  • 如果 next 还没有访问过，就加入队列继续搜索。

4. 代码

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int numSquares(int n) {
        // 1. 定义队列，用来进行 BFS
        Queue<Integer> queue = new LinkedList<>();

        // 2. visited[i] 表示数字 i 是否已经访问过
        boolean[] visited = new boolean[n + 1];

        // 3. 从 n 开始搜索
        queue.offer(n);
        visited[n] = true;

        // step 表示当前用了几个完全平方数
        int step = 0;

        // 4. BFS 搜索
        while (!queue.isEmpty()) {
            int size = queue.size();

            // 每进入一层，表示多使用一个完全平方数
            step++;

            // 只处理当前这一层的节点
            for (int i = 0; i < size; i++) {
                int cur = queue.poll();

                // 枚举所有小于等于 cur 的完全平方数
                for (int j = 1; j * j <= cur; j++) {
                    int next = cur - j * j;

                    // 如果减到 0，说明找到了答案
                    if (next == 0) {
                        return step;
                    }

                    // 如果这个数字没有访问过，就加入队列
                    if (!visited[next]) {
                        visited[next] = true;
                        queue.offer(next);
                    }
                }
            }
        }

        return step;
    }
}

5. 复杂度分析

时间复杂度：O(nn)O(n \sqrt n)

说明：最多访问 0 ~ n 中的每个数字，每个数字最多枚举 sqrt(n) 个完全平方数。

空间复杂度：O(n)O(n)

说明：需要队列和 visited 数组，最多存储 n 个状态。

评论