





'''simple docstring'''




class UpperCAmelCase       :



    def __init__(  self					):
     __UpperCAmelCase					=   ''
     __UpperCAmelCase					=   ''
     __UpperCAmelCase					=   []



    def 					__lowerCamelCase						(  self     ,			__A     ,			__A					):






     if m == -1:
      return n + 1
     elif n == -1:
      return m + 1
     elif self.dp[m][n] > -1:
      return self.dp[m][n]
     else:
      if self.worda[m] == self.worda[n]:
       __UpperCAmelCase					=   self.__min_dist_top_down_dp(m - 1     ,			n - 1					)
      else:
       __UpperCAmelCase					=   self.__min_dist_top_down_dp(_SCREAMING_SNAKE_CASE     ,			n - 1					)
       __UpperCAmelCase					=   self.__min_dist_top_down_dp(m - 1     ,			_SCREAMING_SNAKE_CASE					)
       __UpperCAmelCase					=   self.__min_dist_top_down_dp(m - 1     ,			n - 1					)
       __UpperCAmelCase					=   1 + min(_SCREAMING_SNAKE_CASE     ,			_SCREAMING_SNAKE_CASE     ,			_SCREAMING_SNAKE_CASE					)

      return self.dp[m][n]



    def 					__lowerCamelCase						(  self     ,			__A     ,			__A					):
     __UpperCAmelCase					=   worda
     __UpperCAmelCase					=   worda
     __UpperCAmelCase					=   [[-1 for _ in range(len(_SCREAMING_SNAKE_CASE					)					)] for _ in range(len(_SCREAMING_SNAKE_CASE					)					)]

     return self.__min_dist_top_down_dp(len(_SCREAMING_SNAKE_CASE					) - 1     ,			len(_SCREAMING_SNAKE_CASE					) - 1					)




    def 					__lowerCamelCase						(  self     ,			__A     ,			__A					):
     __UpperCAmelCase					=   worda
     __UpperCAmelCase					=   worda
     __UpperCAmelCase					=   len(_SCREAMING_SNAKE_CASE					)
     __UpperCAmelCase					=   len(_SCREAMING_SNAKE_CASE					)
     __UpperCAmelCase					=   [[0 for _ in range(n + 1					)] for _ in range(m + 1					)]

     for i in range(m + 1					):
      for j in range(n + 1					):
       if i == 0:  # first string is empty
        __UpperCAmelCase					=   j
       elif j == 0:  # second string is empty
        __UpperCAmelCase					=   i
       elif worda[i - 1] == worda[j - 1]:  # last characters are equal
        __UpperCAmelCase					=   self.dp[i - 1][j - 1]
       else:
        __UpperCAmelCase					=   self.dp[i][j - 1]
        __UpperCAmelCase					=   self.dp[i - 1][j]
        __UpperCAmelCase					=   self.dp[i - 1][j - 1]
        __UpperCAmelCase					=   1 + min(_SCREAMING_SNAKE_CASE     ,			_SCREAMING_SNAKE_CASE     ,			_SCREAMING_SNAKE_CASE					)
     return self.dp[m][n]


if __name__ == "__main__":
    _A:					Union[str, Any]							=				EditDistance()

    print("""****************** Testing Edit Distance DP Algorithm ******************""")
    print()

    _A:					List[Any]							=				input("""Enter the first string: """).strip()
    _A:					int							=				input("""Enter the second string: """).strip()

    print()
    print(F"""The minimum edit distance is: {solver.min_dist_top_down(Sa, Sa)}""")
    print(F"""The minimum edit distance is: {solver.min_dist_bottom_up(Sa, Sa)}""")
    print()
    print("""*************** End of Testing Edit Distance DP Algorithm ***************""")












'''simple docstring'''




from __future__ import annotations







def _lowerCAmelCase     (      _lowerCAmelCase    )->     int:
 if not nums:
  return 0
 __UpperCAmelCase					=   nums[0]
 __UpperCAmelCase					=   0
 for num in nums[1:]:
  __UpperCAmelCase					,    __UpperCAmelCase					=   (
      max_excluding + num,
      max(_lowerCAmelCase       ,    _lowerCAmelCase    ),
  )
 return max(_lowerCAmelCase       ,    _lowerCAmelCase    )


if __name__ == "__main__":
    import doctest

    doctest.testmod()





