LeetCode Hot100刷题——完全平方数

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

---

思路分析

本题要求将整数 n 分解为若干个完全平方数的和，并返回所需完全平方数的最少数量。这是一个经典的动态规划问题，可以类比为完全背包问题。

• 物品：完全平方数（如1，4，9，16...），每个物品可以无限次使用
• 背包容量：目标整数n。
• 目标：恰好装满背包所需的最少物品数量。

动态规划步骤

1. 状态定义：定义 dp[i] 表示和为 i 时所需的最少完全平方数数量。
2. 初始化：
   1. dp[0] = 0（和为0时不需要任何平方数）。
   2. 其他位置初始化为一个较大的值（如 n + 1），因为最多由 n 个1组成。（因为要求最小值，所以初始化为一个大于可能最大值的数，比如n+1，因为最多就是n个1相加）。
3. 状态转移：
   1. 对于每个 i（从1到n），遍历所有可能的平方数 j * j（其中 j * j <= i）。
   2. 状态转移方程：dp[i] = min(dp[i], dp[i - j * j] + 1)。
4. 最终结果：dp[n]即为答案。

优化

• 内层循环只需遍历 j 从 1 到 sqrt(i) ，避免无效计算。
• 时间复杂度：O(n√n)，空间复杂度：O(n)。

---

完整代码

class Solution {public int numSquares(int n) {// 创建dp数组，dp[i]表示和为i所需的最少完全平方数的个数int[] dp = new int[n + 1];// 初始化dp数组，初始值设为n+1（一个大于最大可能值的数）for(int i = 0; i <= n; i++){dp[i] = n + 1;      // 初始化为最大值}dp[0] = 0;// 动态规划填表for(int i = 1; i <= n; i++){// 遍历所有平方数 j*j（j从1开始，直到 j*j<=i）for(int j = 1; j * j <= i; j++){dp[i] = Math.min(dp[i], dp[i - j * j] + 1);}}// 返回结果return dp[n];}
}

代码解析

1. 初始化：

   • dp[0] = 0 表示和为 0 时不需要任何平方数。

   • 其他 dp[i] 初始化为 n + 1（因为最多需要 n 个 1，所以 n + 1 是一个安全的上界）。

2. 动态规划填表：

   • 外层循环遍历 i 从 1 到 n，计算每个 i 所需的最少平方数。

   • 内层循环遍历所有可能的平方数 j * j（j 从 1 开始，直到 j * j > i 停止）。

   • 对于每个 j，尝试使用平方数 j * j，更新 dp[i] 为 dp[i - j * j] + 1 的最小值。

3. 返回结果：

   • 最终 dp[n] 存储了和为 n 所需的最少完全平方数数量。

示例验证

• 示例 1（n = 12）：

  • 计算过程：dp[12] = min(dp[11]+1, dp[8]+1, dp[3]+1) → 最终得到 3（4+4+4）。

• 示例 2（n = 13）：

  • 计算过程：dp[13] = min(dp[12]+1, dp[9]+1, dp[4]+1) → 最终得到 2（4+9）。