LeetCode 热题 100 279. 完全平方数

LeetCode 热题 100 | 279. 完全平方数

大家好，今天我们来解决一道经典的动态规划问题——完全平方数。这道题在 LeetCode 上被标记为中等难度，要求找到和为给定整数 n 的完全平方数的最少数量。

---

问题描述

给定一个整数 n，返回和为 n 的完全平方数的最少数量。

示例 1：

输入：n = 12
输出：3
解释：12 = 4 + 4 + 4

示例 2：

输入：n = 13
输出：2
解释：13 = 4 + 9

提示：

• 1 <= n <= 10^4

---

解题思路

核心思想

1. 动态规划：

   • 使用动态规划（DP）来解决这个问题。
   • 定义 dp[i] 为和为 i 的完全平方数的最少数量。
   • 状态转移方程为：
     [
     dp[i] = \min_{j^2 \leq i} (dp[i - j^2] + 1)
     ]
     其中，j^2 是小于等于 i 的完全平方数。

2. 初始化：

   • dp[0] = 0，因为和为 0 的完全平方数的最少数量是 0。
   • dp[1] = 1，因为和为 1 的完全平方数的最少数量是 1。

3. 遍历：

   • 从 2 到 n 遍历，对于每个 i，找到所有小于等于 i 的完全平方数 j^2，并更新 dp[i]。

---

状态转移方程的推导

1. 定义状态

dp[i] 表示和为 i 的完全平方数的最少数量。

2. 状态转移

假设我们已经知道了所有小于 i 的 dp 值，现在需要计算 dp[i]。为了得到和为 i 的完全平方数的最少数量，我们可以尝试以下方法：

• 选择一个完全平方数：选择一个完全平方数 j^2，使得 j^2 <= i。
• 计算剩余部分：如果选择了 j^2，那么剩下的部分就是 i - j^2。
• 递归关系：因此，dp[i] 可以表示为 dp[i - j^2] + 1，其中 +1 表示我们选择了一个完全平方数 j^2。

3. 选择最优解

由于 j^2 有多种可能（例如 1, 4, 9, 16 等），我们需要在所有可能的 j^2 中选择一个使得 dp[i - j^2] + 1 最小的值。因此，状态转移方程为：

[
dp[i] = \min_{j^2 \leq i} (dp[i - j^2] + 1)
]

详细解释

假设我们正在计算 dp[12]，即和为 12 的完全平方数的最少数量。我们可以尝试以下完全平方数：

• 选择 j^2 = 1：

  • 剩下的部分是 12 - 1 = 11。
  • 因此，dp[12] = dp[11] + 1。

• 选择 j^2 = 4：

  • 剩下的部分是 12 - 4 = 8。
  • 因此，dp[12] = dp[8] + 1。

• 选择 j^2 = 9：

  • 剩下的部分是 12 - 9 = 3。
  • 因此，dp[12] = dp[3] + 1。

• 选择 j^2 = 16：

  • 但 16 > 12，所以不能选择。

我们需要在这些选择中找到最小值：

[
dp[12] = \min(dp[11] + 1, dp[8] + 1, dp[3] + 1)
]

Python代码实现

class Solution(object):def numSquares(self, n):""":type n: int:rtype: int"""dp = [0] * (n + 1)dp[0] = 0dp[1] = 1for i in range(2, n + 1):temp = []j = 1while j * j <= i:temp.append(dp[i - j * j])j += 1dp[i] = min(temp) + 1return dp[n]

代码解析

1. 初始化：

   • dp 数组初始化为长度为 n + 1 的列表，所有值初始化为 0。
   • dp[0] = 0，因为和为 0 的完全平方数的最少数量是 0。
   • dp[1] = 1，因为和为 1 的完全平方数的最少数量是 1。

2. 状态转移：

   • 遍历从 2 到 n 的每个整数 i。
   • 对于每个 i，找到所有小于等于 i 的完全平方数 j^2。
   • 将 dp[i - j^2] 的值存储到临时列表 temp 中。
   • 更新 dp[i] 为 min(temp) + 1，表示选择一个完全平方数 j^2 后的最小值。

3. 返回结果：

   • 最终结果存储在 dp[n] 中。

---

复杂度分析

• 时间复杂度：O(n * sqrt(n))，其中 n 是给定的整数。对于每个 i，需要遍历所有小于等于 i 的完全平方数。
• 空间复杂度：O(n)，使用了长度为 n + 1 的 dp 数组。

---

示例运行

示例 1

输入：n = 12
输出：3
解释：12 = 4 + 4 + 4

示例 2

输入：n = 13
输出：2
解释：13 = 4 + 9

---

总结

通过动态规划的方法，我们可以高效地解决完全平方数问题。状态转移方程 dp[i] = \min_{j^2 \leq i} (dp[i - j^2] + 1) 确保了我们能够找到和为 i 的完全平方数的最少数量。希望这篇题解对大家有所帮助，如果有任何问题，欢迎在评论区留言讨论！

关注我，获取更多算法题解和编程技巧！