title: Memoization using dictionary
body: <p>So I am trying to implement Lowest common subsequence in Python and was trying this alternative to my previous solution. I tried using a dictionary instead of a 2-D matrix to memoize the results.</p>
  
  <pre><code>def lcs(s1, s2):
  
      cache = {}
      if len(s1) == 0 or len(s2) == 0:
          return 0
      if (s1, s2) in cache:
          return cache[s1, s2]
      else:
          if s1[-1] == s2[-1]:
              cache[s1, s2] = 1 + lcs(s1[:-1], s2[:-1])
          else:
              cache[s1, s2] = max(lcs(s1[:-1], s2), lcs(s1, s2[:-1]))
      print cache
  </code></pre>
  
  <p>It's returning</p>
  
  <pre><code>TypeError: unsupported operand type(s) for +: 'int' and 'NoneType'
  </code></pre>
  
  <p>which I understand is because I am not returning anything so how can I do something like this.</p>
  
  <pre><code>return cache[s1, s2] = 1 + lcs(s1[:-1], s2[:-1])
  </code></pre>
  
  <p>And I am trying to implement it without using any decorators.</p>