递归实现最长递增子序列(LIS)添加缓存后结果错误如何解决

• 你的猜测准确，最核心的问题是缓存键值不匹配：你为(l[i], i+1)这个键存储的是[l[i]] + lgsMemo(l[i], l, i+1)的拼接结果，但这个键对应的实际函数返回值应该是不带前缀[l[i]]的递归结果，后续再次调用lgsMemo(l[i], l, i+1)时会直接拿到带前缀的错误值，导致结果出现重复元素。
• 缓存写入逻辑错误：你只在长度比较的分支里写入缓存，且写入的是(x,i+1)/(l[i],i+1)的缓存，没有为当前函数调用的键(x,i)存储正确的返回值，同时漏掉了当前元素不大于x场景的缓存写入。
• 全局缓存没有重置机制：多次调用lgs处理不同输入时，全局缓存的旧数据会干扰新计算的结果。

import numpy as np

def lgs(l):
    # 缓存放到函数内部，每次调用重新初始化，避免不同输入互相干扰
    cache = {}
    def lgsMemo(x, i):
        key = (x, i)
        if key in cache:
            return cache[key]
        
        if i >= len(l):
            res = []
        else:
            # 不选当前元素的最长子序列
            list1 = lgsMemo(x, i+1)
            # 符合条件时，选当前元素的最长子序列
            if l[i] > x:
                list2 = [l[i]] + lgsMemo(l[i], i+1)
                list1 = list2 if len(list2) > len(list1) else list1
            res = list1
        # 所有分支统一为当前键写入正确的返回值
        cache[key] = res
        return res
    return lgsMemo(np.NINF, 0)

assert(lgs([1, 20, 3, 7, 40, 5, 2]) == [1,3,7,40])

• 键值匹配校验：缓存的键必须是函数入参的唯一组合，缓存的值必须是该入参组合下函数的原生返回值，不能是经过额外运算后的结果。
• 全分支写入校验：所有函数退出分支都要写入缓存，不要仅在部分条件分支里做缓存写入操作。
• 缓存生命周期校验：如果函数需要支持多次调用不同输入，不要使用全局缓存，建议将缓存封装在外层函数内部，每次调用重新初始化。
• 可变对象校验：如果函数返回列表、字典这类可变对象，必要时返回对象副本，避免缓存的值被外部修改导致后续调用出错。

内容的提问来源于stack exchange，提问作者timo fabregat