ylun.ca - 11 months ago 73

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

`>>>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 Source

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.