new_contents: """
  Author  : Alexander Pantyukhin
  Date    : October 14, 2022
  This is implementation Dynamic Programming up bottom approach
  to find edit distance.
  The aim is to demonstate up bottom approach for solving the task.
  The implementation was tested on the
  leetcode: https://leetcode.com/problems/edit-distance/
  """
  
  """
  Levinstein distance
  Dynamic Programming: up -> down.
  """
  
  
  def min_distance_up_bottom(word1: str, word2: str) -> int:
      """
      >>> min_distance_up_bottom("intention", "execution")
      5
      >>> min_distance_up_bottom("intention", "")
      9
      >>> min_distance_up_bottom("", "")
      0
      >>> min_distance_up_bottom("zooicoarchaeologist", "zoologist")
      10
      """
  
      from functools import lru_cache
  
      len_word1 = len(word1)
      len_word2 = len(word2)
  
      @lru_cache(maxsize=None)
      def min_distance(index1: int, index2: int) -> int:
          # if first word index is overflow - delete all from the second word
          if index1 >= len_word1:
              return len_word2 - index2
          # if second word index is overflow - delete all from the first word
          if index2 >= len_word2:
              return len_word1 - index1
          diff = int(word1[index1] != word2[index2])  # current letters not identical
          return min(
              1 + min_distance(index1 + 1, index2),
              1 + min_distance(index1, index2 + 1),
              diff + min_distance(index1 + 1, index2 + 1),
          )
  
      return min_distance(0, 0)
  
  
  if __name__ == "__main__":
      import doctest
  
      doctest.testmod()
  
subject: add Levinstein distance with Dynamic Programming: up -> down approach (#7171)