完美平方数问题 - 递归解法与记忆化 记忆化是一种优化技术，用于存储中间结果以避免重复计算。在解决完美平方数问题时，递归解法结合记忆化可以提高算法的效率。 完美平方数问题是指给定一个正整数n，找到最少的完全平方数（例如1、4、9、16等），使它们的和等

下面是一个使用递归和记忆化的完美平方数问题的解法的示例代码（使用Python语言实现）：

def numSquares(n):
    memo = [-1] * (n + 1)
    return helper(n, memo)

def helper(n, memo):
    # 检查是否已经计算过
    if memo[n] != -1:
        return memo[n]
    
    # 如果n是完全平方数，返回1
    if int(n ** 0.5) ** 2 == n:
        memo[n] = 1
        return 1
    
    # 遍历所有完全平方数
    min_count = float('inf')
    i = 1
    while i * i <= n:
        count = helper(n - i * i, memo) + 1
        min_count = min(min_count, count)
        i += 1
    
    # 存储中间结果
    memo[n] = min_count
    return min_count

# 测试
print(numSquares(12))  # 输出2，12 = 4 + 4 + 4
print(numSquares(13))  # 输出2，13 = 4 + 9

在上述代码中，我们通过定义一个memo数组来存储已经计算过的中间结果，初始时所有元素都设置为-1。在递归函数helper(n, memo)中，我们首先检查memo[n]是否已经计算过，如果是，则直接返回memo[n]。接着，我们判断n是否是完全平方数，如果是，则返回1。否则，我们遍历从1到sqrt(n)的所有完全平方数k，递归调用helper(n - k * k, memo)，并将结果加1。最后，我们找到最小的结果并存储在memo[n]中，然后返回memo[n]作为最终结果。

这个解法可以大大提高算法的效率，因为通过记忆化技术，我们避免了重复计算相同的子问题，只需计算一次并将结果存储在memo数组中，后续使用时可以直接查找。这样可以减少递归的深度和计算量，提高算法的执行速度。