当前位置：首页 > news >正文

【LeetCode 热题 100】279. 完全平方数——（解法三）空间优化

news 2025/8/21 12:38:19

Problem: 279. 完全平方数

文章目录

整体思路
完整代码
时空复杂度
- 时间复杂度：O(n * sqrt(n))
- 空间复杂度：O(n)

整体思路

这段代码同样旨在解决 “完全平方数” 问题，它采用的是一种经过空间优化的 自底向上（Bottom-Up）动态规划 方法。这是解决此问题最标准和高效的迭代实现之一。

与使用二维DP数组 dp[i][j] 的版本相比，此算法通过一个一维数组 dp[j] 实现了状态压缩，将空间复杂度从 O(N * sqrt(N)) 优化到了 O(N)。

问题模型：完全背包
- 此算法的底层模型依然是 完全背包问题。
  - 背包容量：目标整数 n。
  - 物品：完全平方数 1^2, 2^2, 3^2, ...。
  - 目标：用最少的物品（平方数）填满容量为 n 的背包。
状态定义（一维）
- 算法定义了一个一维DP数组 dp。
- dp[j] 的含义是：和为 j 的最少完全平方数的数量。
- 这个定义比二维版本更直接，它不关心具体是用了“前几个”平方数，只关心凑成 j 这个结果。
状态转移与循环设计
- 初始化：
  - dp 数组被初始化为一个极大值（Integer.MAX_VALUE），表示在计算开始前，凑成任何正整数都是“不可能的”。
  - dp[0] = 0 是关键的基础情况，表示凑成和为0需要0个平方数。
- 遍历顺序：
  - 外层循环 for (int i = 1; i * i <= n; i++)：这个循环遍历的是“物品”，即每个完全平方数 i*i。
  - 内层循环 for (int j = i * i; j <= n; j++)：这个循环遍历的是“背包容量”，即目标和 j。
- 状态转移方程：
  dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
  这行代码是算法的核心。对于每个目标和 j 和当前考虑的平方数 i*i，它在做决策：
  - dp[j] (在 Math.min 的第一个参数位置)：代表不使用当前平方数 i*i 来凑成 j 时，已知的最优解（这个解是基于之前更小的平方数计算得到的）。
  - dp[j - i * i] + 1：代表使用当前平方数 i*i 来凑成 j。如果用了 i*i，那么问题就转化为“用最少的平方数凑成 j - i*i”，其解是 dp[j - i*i]，然后再加1（因为我们用掉了 i*i 这一个数）。
- 完全背包的体现：内层循环 j 是从 i*i 从小到大遍历的。这确保了在计算 dp[j] 时，我们所依赖的 dp[j - i*i] 可能是在本次外层循环中刚刚被更新过的。这意味着同一个平方数 i*i 的贡献可以被累加，从而实现了“完全背包”中物品可无限次使用的特性。
返回结果
- 当所有循环结束后，dp[n] 中就存储了用所有小于等于 n 的平方数凑成 n 所需的最少数量。

完整代码

import java.util.Arrays;class Solution {/*** 计算和为 n 的最少完全平方数的数量（空间优化版）。* @param n 目标整数* @return 最少完全平方数的数量*/public int numSquares(int n) {// dp: 一维动态规划数组。// dp[j] 表示和为 j 的最少完全平方数的数量。int[] dp = new int[n + 1];// 初始化：假设凑成任何数都需要无穷多个平方数。Arrays.fill(dp, Integer.MAX_VALUE);// 基础情况：和为 0 需要 0 个平方数。dp[0] = 0;// 外层循环：遍历所有可用的“物品”，即完全平方数。// i*i 是当前考虑的平方数。for (int i = 1; i * i <= n; i++) {// 内层循环：遍历所有可能的“背包容量”，即目标和 j。// j 从 i*i 开始，因为小于 i*i 的 j 不可能包含 i*i。for (int j = i * i; j <= n; j++) {// 状态转移方程：// 决策是否使用 i*i 这个平方数来构成 j。// dp[j] 的新值 = min(不使用 i*i 的最优解, 使用 i*i 的最优解)// dp[j] (旧值)         -> 不使用 i*i 的情况// dp[j - i*i] + 1      -> 使用 i*i 的情况dp[j] = Math.min(dp[j], dp[j - i * i] + 1);}}// 循环结束后，dp[n] 中存储的就是最终答案。return dp[n];}
}

时空复杂度

时间复杂度：O(n * sqrt(n))

循环结构：算法使用了嵌套循环。
- 外层 for 循环的 i 从 1 增长到 (int)Math.sqrt(n)。因此，它执行了大约 sqrt(n) 次。
- 内层 for 循环的 j 从 i*i 遍历到 n。其执行次数为 n - i*i + 1。
计算依据：
- 总的操作次数是所有内层循环执行次数的总和。
- 总次数 ≈ Σ (从 i=1 到 sqrt(n)) of (n - i*i)。
- 这是一个多项式求和，其最高阶项由 n * sqrt(n) 主导。