一、题目描述

给你一个整数 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

二、解题思路

这是一个典型的动态规划问题。我们可以使用一个数组 dp 来保存到每个数 i 的最少的完全平方数数量。对于每个数 i，我们需要考虑所有小于等于 i 的完全平方数 jj（其中 jj <= i），然后找出 dp[i - j*j] + 1 的最小值。

以下是具体的步骤：

1. 初始化一个长度为 n+1 的数组 dp，所有元素初始化为最大值（比如 Integer.MAX_VALUE），因为我们要找最小值。
2. dp[0] 应该初始化为 0，因为 0 可以由 0 个完全平方数组成。
3. 对于每个数 i（从 1 到 n），我们需要检查所有可能的完全平方数 jj（其中 jj <= i）。
4. 对于每个 jj，我们将 dp[i] 更新为 min(dp[i], dp[i - jj] + 1)。
5. 最终，dp[n] 就是我们要求的答案。

三、具体代码

class Solution {public int numSquares(int n) {// dp[i] 表示和为 i 的完全平方数的最少数量int[] dp = new int[n + 1];// 初始化 dp 数组Arrays.fill(dp, Integer.MAX_VALUE);// 0 可以由 0 个完全平方数组成dp[0] = 0;// 计算每个数的最少完全平方数数量for (int i = 1; i <= n; i++) {// 检查所有可能的完全平方数 j*jfor (int j = 1; j * j <= i; j++) {dp[i] = Math.min(dp[i], dp[i - j * j] + 1);}}// 返回和为 n 的完全平方数的最少数量return dp[n];}
}

四、时间复杂度和空间复杂度

1. 时间复杂度

• 初始化 dp 数组的时间复杂度为 O(n)，因为我们需要对 n+1 个元素进行填充操作。

• 外层循环 for (int i = 1; i <= n; i++) 运行 n 次，因为它遍历了从 1 到 n 的每一个整数。

• 内层循环 for (int j = 1; j * j <= i; j++) 的运行次数依赖于 i 的值。对于每个 i，j 的最大值为 sqrt(i)，因此内层循环的运行次数随着 i 的增加而减少。

• 当 i 较小时，sqrt(i) 接近 i，内层循环接近 i 次；当 i 较大时，sqrt(i) 接近 sqrt(n)，内层循环接近 sqrt(n) 次。

• 平均来看，内层循环的运行次数大约为 sqrt(i)，所以我们可以将内层循环的总运行次数估计为所有 i 的 sqrt(i) 之和，即 sqrt(1) + sqrt(2) + … + sqrt(n)。由于 sqrt(i) 是一个递增函数，我们可以将其总和估计为小于 n * sqrt(n)。

因此，总的时间复杂度为 O(n) + O(n * sqrt(n))，简化后为 O(n * sqrt(n))。

2. 空间复杂度

• dp 数组的大小为 n+1，因此需要 O(n) 的空间来存储所有的 dp 值。

• 除了 dp 数组外，代码中没有使用额外的空间，所有的变量都是常数级别的空间。

因此，总的空间复杂度为 O(n)。

五、总结知识点

• 动态规划 (Dynamic Programming, DP):

  • 动态规划是一种算法设计技术，用于求解具有重叠子问题和最优子结构的问题。
  • dp 数组用于存储子问题的解，避免重复计算。

• 数组的初始化:

  • 使用 new int[n + 1] 创建一个整型数组 dp，其长度为 n + 1。
  • 使用 Arrays.fill(dp, Integer.MAX_VALUE) 初始化数组 dp 的所有元素为 Integer.MAX_VALUE，表示初始时没有找到解。

• 基础循环结构:

  • 两个嵌套的 for 循环用于遍历所有可能的数和它们的完全平方数。

• 数学运算:

  • 使用 j * j 计算完全平方数。
  • 使用 Math.min 函数来找出当前问题的最小解。

• 数组的索引操作:

  • 通过索引 i 和 i - j * j 访问和更新 dp 数组。

• 递推关系:

  • dp[i] = Math.min(dp[i], dp[i - j * j] + 1) 表示状态转移方程，用于更新 dp[i] 为最小的完全平方数数量。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。