How do I memoize this LIS python2.7 algorithm properly?
<p>I'm practicing Dynamic Programming and I am writing the Longest Increasing Subsequence problem.</p>

<p>I have the DP solution:</p>

<pre><code>def longest_subsequence(lst, lis=[], mem={}):
  if not lst:
    return lis
  if tuple(lst) not in mem.keys():
    if not lis or lst[0] &gt; 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)]
</code></pre>

<p>And a non-memoized version</p>

<pre><code>def longest_subsequence(lst, lis=[]):
  if not lst:
    return lis
  if not lis or lst[0] &gt; 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
</code></pre>

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

<pre><code>&gt;&gt;&gt; longest_subsequence([10,9,2,5,3,7,101,18])
[10, 101]
</code></pre>

<p>The non-memoized version is fully correct however (although much slower). </p>

<pre><code>&gt;&gt;&gt; longest_subsequence([10,9,2,5,3,7,101,18])
[2, 5, 7, 101]
</code></pre>

<p>what I am doing wrong?</p>

<p><strong>EDIT:</strong> Tempux's answer fails on the following:</p>

<pre><code>&gt;&gt;&gt; longest_subsequence([3,5,6,2,5,4,19,5,6,7,12])
[3, 5, 6, 7, 12]
</code></pre>

<p>where the solution the non-memoized version is:</p>

<pre><code>&gt;&gt;&gt; longest_subsequence([3,5,6,2,5,4,19,5,6,7,12])
[3, 4, 5, 6, 7, 12]
</code></pre>

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

<pre><code>def longest_subsequence(lst, prev=None, mem={}):
  if not lst:
    return []
  if (tuple(lst),prev) not in mem:
    if not prev or lst[0] &gt; 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])
</code></pre>

<p>Note that using the <code>tuple(list)</code> as your dynamic state is not a very good idea. You can simply use the index of the item in the <code>list</code> that you are checking instead of the whole list:</p>

<pre><code>def longest_subsequence(lst, index=0, prev=None, mem={}):
  if index&gt;=len(lst):
    return []
  if (index,prev) not in mem:
    if not prev or lst[index] &gt; 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])
</code></pre>

<p>For more efficient approaches you can check <a href="http://stackoverflow.com/questions/2631726/how-to-determine-the-longest-increasing-subsequence-using-dynamic-programming">this</a> question.</p>

python algorithm dynamic-programming memoization