ylun.ca - 10 days ago 5x
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?

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.