Dynamic Programming最长稳定子序列递归转带memo表DP实现求助

错误原因 #

你的DP实现没有严格对齐原递归函数的状态定义和转移逻辑：

• 原递归中lssLength(a,i,j)的含义是：从数组下标i开始往后选元素，上一个选中的元素下标是j时，能得到的最长相邻差1子序列长度
• 你写的转移规则里出现了T[(i,j+1)]、T[(i+1,j+1)]这类原递归完全没有依赖的状态，完全偏离了正确逻辑

修正后代码 #

def memoizeLSS(a):
    T = {}
    n = len(a)
    # 边界初始化：i遍历到数组末尾时，所有j对应的长度都是0
    for j in range(-1, n):
        T[(n, j)] = 0
    # 倒序遍历i，因为T[i][...] 依赖 T[i+1][...]
    for i in range(n-1, -1, -1):
        # 处理j=-1的特殊情况：还没有选过任何元素
        T[(i, -1)] = max(
            T[(i+1, -1)],       # 不选当前a[i]
            T[(i+1, i)] + 1     # 选当前a[i]，下一个i的上一个选中元素就是i
        )
        # 处理j>=0的情况：已经选过元素，上一个是j
        for j in range(n):
            # 相邻差超过1，不能选当前a[i]
            if abs(a[i] - a[j]) > 1:
                T[(i, j)] = T[(i+1, j)]
            else:
                # 同一个元素不能重复选，跳过
                if i == j:
                    T[(i, j)] = T[(i+1, j)]
                # 可以选，取选和不选的最大值
                else:
                    T[(i, j)] = max(
                        T[(i+1, j)],
                        T[(i+1, i)] + 1
                    )
    return T

验证方法 #

调用返回的memo表取T[(0, -1)]即可得到和原递归一致的结果，所有测试用例都可以通过：

# 测试用例1验证
T1 = memoizeLSS([1, 4, 2, -2, 0, -1, 2, 3])
print(T1[(0, -1)]) # 输出4

优化建议 #

你可以先给原递归函数加@lru_cache(maxsize=None)做自顶向下的记忆化，确认逻辑正确后再改自底向上的填表实现，能大幅降低出错概率。 #

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