如何正确记忆这个 LIS python2.7 算法？

Question

我正在练习动态规划，我正在写最长递增子序列问题。

我有DP解决方案：

def longest_subsequence(lst, lis=[], mem={}):
  if not lst:
    return lis
  if tuple(lst) not in mem.keys():
    if not lis or lst[0] > lis[-1]:
      mem[tuple(lst)] = max([longest_subsequence(lst[1:], lis+[lst[0]], mem), longest_subsequence(lst[1:], lis, mem)], key=len)
    else:
     mem[tuple(lst)] = longest_subsequence(lst[1:], lis, mem)
  return mem[tuple(lst)]

还有一个非记忆版本

def longest_subsequence(lst, lis=[]):
  if not lst:
    return lis
  if not lis or lst[0] > lis[-1]:
    result = max([longest_subsequence(lst[1:], lis+[lst[0]]), longest_subsequence(lst[1:], lis)], key=len)
  else:
    result = longest_subsequence(lst[1:], lis)
  return result

但是，这两个函数具有不同的行为。例如，测试用例 longest_subsequence([10,9,2,5,3,7,101,18]) 对于 memoized 版本失败。

>>> longest_subsequence([10,9,2,5,3,7,101,18])
[10, 101]

然而，非记忆版本是完全正确的（虽然慢得多）。

>>> longest_subsequence([10,9,2,5,3,7,101,18])
[2, 5, 7, 101]

我做错了什么？

Answer 1

您的状态取决于 lst 和您选择的上一个项目。但是你只考虑了lst。这就是您得到不正确结果的原因。要修复它，您只需将上一个项目添加到您的动态状态。

def longest_subsequence(lst, prev=None, mem={}):
  if not lst:
    return []
  if (tuple(lst),prev) not in mem:
    if not prev or lst[0] > prev:
      mem[(tuple(lst),prev)] = max([[lst[0]]+longest_subsequence(lst[1:], lst[0]), longest_subsequence(lst[1:], prev)], key=len)
    else:
     mem[(tuple(lst),prev)] = longest_subsequence(lst[1:], prev)

  return mem[(tuple(lst),prev)]

print longest_subsequence([3,5,6,2,5,4,19,5,6,7,12])

请注意，使用 tuple(list) 作为动态状态并不是一个好主意。您可以简单地使用您正在检查的 list 中的项目索引而不是整个列表：

def longest_subsequence(lst, index=0, prev=None, mem={}):
  if index>=len(lst):
    return []
  if (index,prev) not in mem:
    if not prev or lst[index] > prev:
      mem[(index,prev)] = max([[lst[index]]+longest_subsequence(lst, index+1, lst[index]), longest_subsequence(lst, index+1, prev)], key=len)
    else:
      mem[(index,prev)] = longest_subsequence(lst,index+1, prev)

  return mem[(index,prev)]

print longest_subsequence([3,5,6,2,5,4,19,5,6,7,12])

如需更有效的方法，您可以查看 this 问题。

Answer 2

所以我刚刚发现 Tempux 的答案并不适用于所有情况。

我回过头来将整个状态封装到记忆字典中，因此将 tuple(lis) 添加为密钥的一部分。此外，lst 索引技巧可能不那么容易实现，因为我通过递归改变 lst，因此我使用 tuple() 作为我的键。

我这样做的原因是多个 lis 可能具有相同的 [-1] 值。因此，对于这个新状态，代码是：

def longest_subsequence(lst, lis=[],mem={}):
  if not lst:
    return lis
  if (tuple(lst),tuple(lis)) not in mem:
    if not lis or lst[0] > lis[-1]:
      mem[(tuple(lst),tuple(lis))] = max([longest_subsequence(lst[1:], lis+[lst[0]]), longest_subsequence(lst[1:], lis)], key=len)
    else:
     mem[(tuple(lst),tuple(lis))] = longest_subsequence(lst[1:], lis)
  return mem[(tuple(lst),tuple(lis))]

这适用于我目前测试过的所有情况。

如何正确记忆这个 LIS python2.7 算法？

How do I memoize this LIS python2.7 algorithm properly?

python

algorithm

dynamic-programming

memoization