Leetcode-100 完全平方数

和为n的完全平方数

解题思路

本问题可以采用**记忆化搜索（DFS + Memoization）**的方法解决，核心思路是通过递归遍历所有可能的平方数组合，利用缓存避免重复计算。关键点在于将问题分解为子问题：对于每个可能的平方数i²，选择或不选择该数，并递归求解剩余部分。

算法步骤

1. 问题分解：将问题转化为在平方数列表中选择若干数，使其和为n，求最少选择个数。平方数列表为[1,4,9,…,k²]，其中k = isqrt(n)
2. 递归定义：定义dfs(i, j)表示用前i个平方数（即1²,2²,…,i²）组成和j的最少数量
3. 递归逻辑：
   • 终止条件：当i=0时，只有j=0时有解（返回0），否则无解（返回无穷大）
   • 剪枝优化：当当前平方数i² > j时，只能不选i²
   • 状态转移：比较选择和不选择i²的情况，取最小值
4. 记忆化优化：通过@cache缓存中间结果，避免重复计算

具体例子分析

以n=12为例：

1. 最大平方数为3²=9，初始调用dfs(3, 12)
2. 递归树展开：
   • 选择3²：剩余12-9=3 → dfs(3,3)+1
   • 不选3²：继续考虑2² → dfs(2,12)
3. 最终最优解为3（4+4+4），递归路径如下：
   • dfs(3,12) → dfs(3,3)+1 → dfs(2,3) → dfs(1,3) → dfs(1,2)+1 → dfs(1,1)+1 → dfs(1,0)+1 → 0

代码实现

from math import isqrt
from functools import cache

class Solution:
 def numSquares(self, n: int) -> int:
     @cache
     def dfs(i: int, j: int) -> int:
         if i == 0:
             return float('inf') if j != 0 else 0
         if j < i*i:
             return dfs(i-1, j)
         return min(dfs(i-1, j), dfs(i, j - i*i) + 1)
     
     return dfs(isqrt(n), n)

复杂度分析

• 时间复杂度：O(n * √n)
  每个状态 (i, j) 最多计算一次，其中：

  • i 的范围是 [1, √n]
  • j 的范围是 [0, n]
  • 总状态数为 √n * n
    由于每个状态转移需要 O(1) 时间，总体时间复杂度为 O(n * √n)。

• 空间复杂度：O(n * √n)
  由于使用 记忆化缓存 存储所有可能的状态，需要 O(n * √n) 的空间。

优化

解题思路

本方法通过预计算动态规划表的方式，预先计算出每个数的最小平方数组合，从而在查询时达到O(1)时间复杂度。核心思想是将完全平方数问题转化为完全背包问题，通过动态规划求解。

算法步骤

1. 预计算阶段：

   • 定义最大计算范围N=10000
   • 初始化动态规划数组f，其中f[0]=0，其余初始化为无穷大
   • 遍历所有可能的平方数i²（i从1到√N）
   • 对每个平方数，更新所有可能的值j（从i²到N）

2. 状态转移方程：

   f[j] = \min(f[j],\ f[j-i^2] + 1)
   

表示对于数值j，可以通过选择当前平方数i²来优化结果

3. 查询阶段

• 直接返回预计算结果f[n]

具体例子

以 n = 12 为例，预计算过程如下：

最终结果：
$begin:math:display$
f[12] = 3
$end:math:display$
即 12 可由 3 个完全平方数之和构成，如 4 + 4 + 4。

from math import isqrt
import sys

# 预计算到10000的所有可能值
MAX_N = 10000
f = [0] + [sys.maxsize] * MAX_N  # 初始化：f[0]=0，其他为无穷大

# 动态规划填表
for i in range(1, isqrt(MAX_N) + 1):
    square = i * i
    for j in range(square, MAX_N + 1):
        if f[j - square] + 1 < f[j]:
            f[j] = f[j - square] + 1

class Solution:
    def numSquares(self, n: int) -> int:
        return f[n] if n <= MAX_N else -1  # 处理超出预计算范围的情况

复杂度分析

• 预计算时间复杂度：$O(N\sqrt{N})$

  • 外层循环 执行 $\sqrt{N}$ 次（遍历所有可能的完全平方数）。
  • 内层循环 执行 $N$ 次（遍历 $0$ 到 $N$ 进行状态转移）。
  • 总体复杂度为 $O(N\sqrt{N})$。

• 查询时间复杂度：$O(1)$

  • 直接访问 预计算结果，查询时间为 $O(1)$。

• 空间复杂度：$O(N)$

  • 需要存储 长度为 $N+1$ 的 DP 数组，空间复杂度为 $O(N)$。