如何用记忆化优化LeetCode目标和问题的递归表达式生成代码？

你当前的递归代码能生成所有符号组合，但属于暴力枚举，时间复杂度是O(2^n)，当数组长度较大时会超时。下面直接讲怎么用记忆化优化，避免重复计算相同状态。

原代码与输出 #

nums=[1,1,1]
res=[]
def recursion(i,temp,res):
    if i==len(nums):
        res.append(temp[:])
        return
    temp.append(nums[i])
    recursion(i+1,temp,res)
    temp.pop()
    temp.append(-1*nums[i])
    recursion(i+1,temp,res)
    temp.pop()
recursion(0,[],res)
print(res)

输出：

[[1, 1, 1], [1, 1, -1], [1, -1, 1], [1, -1, -1], [-1, 1, 1], [-1, 1, -1], [-1, -1, 1], [-1, -1, -1]]

记忆化优化思路 #

原代码的问题在于，不同的符号选择路径可能会走到相同的状态：比如处理到第i个元素时，当前累加和为sum_val。这些重复状态会被反复计算，浪费资源。记忆化的核心就是缓存这些状态的结果，下次遇到直接复用，把时间复杂度降到O(n*S)（n是数组长度，S是可能的总和范围）。

下面给出两种优化实现方式：

方式1：用functools.lru_cache快速实现 #

不需要生成所有组合，直接计算能达到目标值的路径数（如果只需要判断是否存在，改返回布尔值即可）：

from functools import lru_cache

nums = [1,1,1]
target = 3  # 替换成你的目标值

@lru_cache(maxsize=None)
def dfs(i, current_sum):
    # 处理完所有元素，判断当前和是否等于目标值
    if i == len(nums):
        return 1 if current_sum == target else 0
    # 选择+当前元素的路径数
    add = dfs(i+1, current_sum + nums[i])
    # 选择-当前元素的路径数
    subtract = dfs(i+1, current_sum - nums[i])
    # 返回两种选择的总路径数
    return add + subtract

# 初始状态：从第0个元素开始，当前和为0
result = dfs(0, 0)
print(f"达到目标值的路径数：{result}")

方式2：手动用字典维护记忆缓存 #

如果不想用装饰器，可以手动实现记忆字典，逻辑更清晰：

nums = [1,1,1]
target = 3
memo = {}  # 缓存(i, current_sum)对应的结果

def dfs(i, current_sum):
    key = (i, current_sum)
    # 先查缓存，存在直接返回
    if key in memo:
        return memo[key]
    # 终止条件
    if i == len(nums):
        res = 1 if current_sum == target else 0
        memo[key] = res
        return res
    # 递归计算两种选择的结果
    add = dfs(i+1, current_sum + nums[i])
    subtract = dfs(i+1, current_sum - nums[i])
    # 存入缓存后返回
    memo[key] = add + subtract
    return memo[key]

result = dfs(0, 0)
print(f"达到目标值的路径数：{result}")

额外说明 #

如果你的需求只是判断是否存在符合条件的符号组合，而不是统计路径数，可以把返回值改成布尔类型：

• 终止条件返回current_sum == target
• 递归时返回add or subtract
  这样同样能利用记忆化优化，而且逻辑更简洁。

内容的提问来源于stack exchange，提问作者Amey-K27