title: Memoization of Recursive function gives wrong answer
body: <p>This is the implementation of the <code>Edit distance</code> problem.</p>
  
  <p>Here is the recursive version without any memoization</p>
  
  <pre><code> def edit_distance(str_a, str_b, len_a, len_b):
      # bot strs consumed
      if len_a == 0 and len_b == 0:
         return 0
  
      if len_a == 0:
         return len_b
  
      if len_b == 0:
         return len_a
  
      i_a = len_a-1
      i_b = len_b-1
  
      if str_a[i_a] == str_b[i_b]:
         return edit_distance(str_a, str_b, i_a, i_b)
  
      replace = edit_distance(str_a, str_b, i_a, i_b)
      delete = edit_distance(str_a, str_b, i_a, len_b)
      insert = edit_distance(str_a, str_b, len_a, i_b)
  
      return 1+min(replace, delete, insert)
  </code></pre>
  
  <p>Now here is the memoized version where I cache the results of call.</p>
  
  <pre><code>def edit_distance_memo(str_a, str_b, len_a, len_b, cache):
    if cache[len_a][len_b] != -1:
      return cache[len_a][len_b]
  
  
    if len_a == 0 and len_b == 0:
      cache[len_a][len_b] = 0
      return 0
  
    if len_a == 0:
      cache[len_a][len_b] = len_b
      return len_b
  
    if len_b == 0:
      cache[len_a][len_b] = len_a
      return len_a
  
    if cache[len_a][len_b] != -1:
      return cache[len_a][len_b]
  
    i_a = len_a-1
    i_b = len_b-1
  
   if str_a[i_a] == str_b[i_b]:
     cache[len_a][len_b] =  edit_distance_memo(str_a, str_b, i_a, i_b, cache)
     return cache[len_a][len_b]
  
   replace = edit_distance_memo(str_a, str_b, i_a, i_b, cache)
   delete = edit_distance_memo(str_a, str_b, i_a, len_b, cache)
   insert = edit_distance_memo(str_a, str_b, len_a, i_b, cache)
  
   best_option = min(replace, delete, insert)
  
   cache[len_a][len_b] = 1 + best_option
  
   return cache[len_a][len_b]
  </code></pre>
  
  <p>Here is the calling code:</p>
  
  <pre><code> from time import time
   str1 = "Shakespeare"
   str2 = "shake spear"
   s1 =  time()
   print edit_distance(str1, str2, len(str1), len(str2)), "edit_distance"
   print "diff---", time()-s1
  
   rows = len("Shakespeare")+1
   columns = len("shake spear")+1
  
   cache = [[-1] * columns] * rows
   st  = time()
   print edit_distance_memo("Shakespeare", "shake spear",len("Shakespeare"), len("shake spear"), cache)
  </code></pre>
  
  <p>For some reason the memoized version, seems to be giving a wrong answer (7 instead of 3). What is wrong here?</p>
  
  <p>Thanks in advance.</p>