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

Question

I'm practicing Dynamic Programming and I am writing the Longest Increasing Subsequence problem.

I have the DP solution:

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)]

And a non-memoized version

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

However, the two functions have different behaviours. For example, the test case longest_subsequence([10,9,2,5,3,7,101,18]) fails for the memoized version.

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

The non-memoized version is fully correct however (although much slower).

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

what I am doing wrong?

Answer 1

Your state depends on both lst and previous item you have picked. But you are only considering the lst. That is why you are getting incorrect results. To fix it you just have to add previous item to your dynamic state.

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])

Note that using the tuple(list) as your dynamic state is not a very good idea. You can simply use the index of the item in the list that you are checking instead of the whole 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])

For more efficient approaches you can check this question.