ylun.ca ylun.ca - 1 month ago 27
Python Question

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

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

Your state depends on both lst and lis[-1]. But you are only considering the lst. That is why you are getting incorrect results. To fix it you just have to add lis[-1] to your dynamic state.

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

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

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.

For more efficient approaches you can check this question.