LeetCode中完全平方数的示例分析

在LeetCode中，完全平方数（Perfect Squares）是一个常见的算法问题。这类问题通常要求我们找到一个数的最少完全平方数的和，或者判断一个数是否可以表示为若干个完全平方数的和。本文将通过几个示例，详细分析这类问题的解决思路和算法实现。

问题描述

LeetCode中的完全平方数问题通常有以下几种形式：

1. 最少完全平方数的和：给定一个正整数 n，找到最少的完全平方数的和等于 n。
2. 判断是否为完全平方数：给定一个正整数 n，判断 n 是否可以表示为若干个完全平方数的和。

本文主要关注第一种问题，即找到最少的完全平方数的和等于 n。

示例分析

示例 1：n = 12

问题描述：给定 n = 12，找到最少的完全平方数的和等于 12。

分析：

首先，我们需要找到所有小于等于 12 的完全平方数。这些完全平方数包括：1, 4, 9。

接下来，我们可以使用动态规划（Dynamic Programming, DP）来解决这个问题。我们定义一个数组 dp，其中 dp[i] 表示组成数字 i 所需的最少完全平方数的个数。

动态规划步骤：

1. 初始化 dp 数组，长度为 n + 1，初始值为无穷大（表示无法组成），dp[0] = 0。
2. 对于每个 i 从 1 到 n，遍历所有小于等于 i 的完全平方数 j，更新 dp[i] = min(dp[i], dp[i - j] + 1)。

具体实现：

def numSquares(n):
    dp = [float('inf')] * (n + 1)
    dp[0] = 0
    for i in range(1, n + 1):
        j = 1
        while j * j <= i:
            dp[i] = min(dp[i], dp[i - j * j] + 1)
            j += 1
    return dp[n]

结果：

对于 n = 12，dp 数组的最终状态为：

dp = [0, 1, 2, 3, 1, 2, 3, 4, 2, 1, 2, 3, 3]

因此，dp[12] = 3，表示 12 可以由 4 + 4 + 4 或 9 + 1 + 1 + 1 组成，最少需要 3 个完全平方数。

示例 2：n = 13

问题描述：给定 n = 13，找到最少的完全平方数的和等于 13。

分析：

同样地，我们首先找到所有小于等于 13 的完全平方数：1, 4, 9。

动态规划步骤：

1. 初始化 dp 数组，长度为 14，初始值为无穷大，dp[0] = 0。
2. 对于每个 i 从 1 到 13，遍历所有小于等于 i 的完全平方数 j，更新 dp[i] = min(dp[i], dp[i - j] + 1)。

具体实现：

def numSquares(n):
    dp = [float('inf')] * (n + 1)
    dp[0] = 0
    for i in range(1, n + 1):
        j = 1
        while j * j <= i:
            dp[i] = min(dp[i], dp[i - j * j] + 1)
            j += 1
    return dp[n]

结果：

对于 n = 13，dp 数组的最终状态为：

dp = [0, 1, 2, 3, 1, 2, 3, 4, 2, 1, 2, 3, 3, 2]

因此，dp[13] = 2，表示 13 可以由 9 + 4 组成，最少需要 2 个完全平方数。

示例 3：n = 18

问题描述：给定 n = 18，找到最少的完全平方数的和等于 18。

分析：

首先，找到所有小于等于 18 的完全平方数：1, 4, 9, 16。

动态规划步骤：

1. 初始化 dp 数组，长度为 19，初始值为无穷大，dp[0] = 0。
2. 对于每个 i 从 1 到 18，遍历所有小于等于 i 的完全平方数 j，更新 dp[i] = min(dp[i], dp[i - j] + 1)。

具体实现：

def numSquares(n):
    dp = [float('inf')] * (n + 1)
    dp[0] = 0
    for i in range(1, n + 1):
        j = 1
        while j * j <= i:
            dp[i] = min(dp[i], dp[i - j * j] + 1)
            j += 1
    return dp[n]

结果：

对于 n = 18，dp 数组的最终状态为：

dp = [0, 1, 2, 3, 1, 2, 3, 4, 2, 1, 2, 3, 3, 2, 3, 4, 1, 2, 2]

因此，dp[18] = 2，表示 18 可以由 9 + 9 组成，最少需要 2 个完全平方数。

总结

通过以上示例分析，我们可以看到，动态规划是解决完全平方数问题的有效方法。通过定义 dp 数组并逐步更新，我们可以找到组成给定数字 n 所需的最少完全平方数的个数。这种方法的时间复杂度为 O(n * sqrt(n))，空间复杂度为 O(n)，适用于大多数情况。

在实际应用中，我们还可以结合数学方法（如四平方和定理）来进一步优化算法，但这超出了本文的范围。希望本文的示例分析能够帮助读者更好地理解完全平方数问题的解决思路。