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

Leetcode 完全平方数

article 2024/10/11 16:49:07

在这里插入图片描述
这段代码是用 动态规划（Dynamic Programming, DP）来解决 LeetCode 第279题「完全平方数」的问题，题目要求给定一个整数 n，找出若干个完全平方数（如1, 4, 9, 16等）的和，恰好等于 n，并且这些数的个数最少。

代码的算法思想可以总结为以下几个步骤：

1. 初始化 DP 数组：

我们创建一个长度为 n+1 的数组 dp，其中 dp[i] 表示能够凑成数字 i 的最少完全平方数的个数。初始化时，将 dp[0] 设为 0，表示凑成数字 0 需要 0 个完全平方数。而其余所有位置的值都初始化为 Integer.MAX_VALUE，表示初始状态下我们还不知道如何凑成这些数值（我们用一个较大的数来初始化，方便后面取最小值）。

2. 预处理所有的完全平方数：

我们需要找到小于或等于 n 的所有完全平方数，比如对于 n=12，我们需要考虑的完全平方数是 1, 4, 9（即 1^2, 2^2, 3^2）。代码通过循环 for (int i = 1; i * i <= n; i++) 来生成这些完全平方数。

3. 更新 DP 数组：

对于每一个完全平方数 square = i * i，我们从 square 开始更新 DP 数组。更新的规则是：
dp[j] = Math.min(dp[j], dp[j - square] + 1)，意思是我们要凑成数字 j，可以通过之前凑成 j - square 的数字，再加上一个 square 来凑成 j，因此我们选择最小的完全平方数组合个数。

例如，假设我们当前有 n=12，其中 square=4（即 2^2），我们可以通过 dp[12] = Math.min(dp[12], dp[12 - 4] + 1) 来更新 dp[12] 的值。

4. 最终结果：

当所有完全平方数都被处理完后，dp[n] 中存储的就是凑成 n 的最少完全平方数的个数。程序最后返回 dp[n] 即可。

举例说明：

对于 n = 12：

1^2 = 1, 2^2 = 4, 3^2 = 9
我们可以得到的最优解是 4 + 4 + 4，即 dp[12] = 3，需要三个完全平方数。

对于 n = 13：

我们可以得到的最优解是 9 + 4，即 dp[13] = 2，需要两个完全平方数。

该算法的时间复杂度：

外层循环运行 sqrt(n) 次，内层循环运行 n 次。因此时间复杂度为 O(n * sqrt(n))，这对于较大的 n 也是一个相对高效的解法。

这个算法的核心思想是利用动态规划，通过之前的计算结果来优化后续的计算，使得每个数 n 都能以最少的完全平方数组合凑成。

java 实现代码：

class Solution {
    public int numSquares(int n) {
        //使用动态规划算法,dp[i]表示凑成和为i所需要的完全平方数的最少数量。
        //首先创建长度为n+1的数组
        int[] dp = new int[n + 1];
        //由于后面需要使用min更新dp, 所以我们初始时将所有元素设为Integer.MAX_VALUE
        Arrays.fill(dp, Integer.MAX_VALUE);
        //初始化dp[0],凑成0需要0个
        dp[0] = 0;

        //然后开始更新dp
        for(int i = 1; i * i <= n; ++i) { 
            //i 只是用来生成平方数的根，用于计算出完全平方数，它并不是我们要更新的目标数。
            //寻找所有不大于 n 的完全平方数
            int square = i * i; //square从1开始
            for(int j = square; j <=n; j++) {
                //这里更新的是dp[j]而不是dp[i],为什么？
                //j 表示当前我们要凑成的数。在内部循环中，我们尝试使用平方数 square 来更新所有大于等于 square 的数字 j
                //dp[j - square] 表示我们已经凑成了 j - square，接下来再加上一个 square 来凑成 j。
                dp[j] = Math.min(dp[j], dp[j - square] + 1);
            }
        }
        return dp[n];
    }
}

对于这一部分代码，为什么更新dp数组时使用dp[j]而不是dp[i]？

        // Precompute all the perfect squares less than or equal to n
        for (int i = 1; i * i <= n; i++) {
            int square = i * i;
            // Update the dp array
            for (int j = square; j <= n; j++) {
                dp[j] = Math.min(dp[j], dp[j - square] + 1);
            }
        }

这是一个非常好的问题！我们需要仔细理解这段代码中的变量 i 和 j 的含义，特别是在动态规划的过程中，为什么我们更新的是 dp[j] 而不是 dp[i]。

1. 变量的含义：

i：循环中的 i 代表生成完全平方数的根。例如，i = 1 代表平方数 1^2 = 1，i = 2 代表平方数 2^2 = 4，以此类推。
square：这是由 i 计算出的平方数，即 square = i * i，它是我们用来凑成数字 j 的完全平方数。
j：j 代表我们正在更新的数字（目标数）。我们试图使用之前计算出的较小的平方数来凑成 j。

2. 为什么更新 `dp[j]` 而不是 `dp[i]`：

i 只是用来生成平方数的根，用于计算出完全平方数 square，它并不是我们要更新的目标数。我们要更新的是那些可以被凑成的数字 j。
j 表示当前我们要凑成的数。在内部循环中，我们希望尝试使用平方数 square 来更新所有大于等于 square 的数字 j（即 j = square, square + 1, ..., n）。

举个例子来说明：

举例：

假设 n = 12，我们已经生成了完全平方数 square = 4（即 i = 2，square = 2^2 = 4），接下来要更新 DP 数组。

我们的目标是通过这个 square = 4 来凑成所有可能的 j，从 4 开始到 12。
例如，我们想通过 square = 4 来更新 dp[5]。我们知道 dp[5 - 4] = dp[1]，而 dp[1] 是已经计算好的，因此我们可以通过 dp[5] = Math.min(dp[5], dp[1] + 1) 来更新 dp[5]，意思是我们可以用 4 + 1 来凑成 5，这是一种新的组合方式。

通过从 square 开始更新所有数字 j，我们可以确保每一个 j 都会考虑到使用平方数 square 来组合的情况，从而找到最优解。

3. 为什么不用 `dp[i]`？

如果你使用 dp[i]，这就意味着你只在更新由 i 直接生成的那个完全平方数，而不是更新所有可能用这个平方数 square 凑成的其他数。例如：

如果你只更新 dp[i]，那只会更新 dp[i * i]，即你只会更新 dp[1], dp[4], dp[9]，而不会更新 dp[5], dp[6], ...，因此很多数的最优解都无法被计算出来。
但是在题目中，很多数（比如 12）可以由多个平方数组合出来（如 12 = 4 + 4 + 4），如果你只更新 dp[i] 而不是 dp[j]，你就无法找到这些组合的最优解。

4. 内外循环的意义：

外层循环：for (int i = 1; i * i <= n; i++) 负责生成所有可能的完全平方数 square = i * i。这些平方数是我们凑成目标数的工具。
内层循环：for (int j = square; j <= n; j++) 负责更新 DP 数组中每个数 j，我们尝试用平方数 square 去凑成这个数 j，并更新 dp[j]。