



'''simple docstring'''




class     UpperCamelCase_				:





 def __init__(						self					)    ->    Dict:
        UpperCAmelCase  :	Any							  =	""""""
        UpperCAmelCase  :	List[str]							  =	""""""
        UpperCAmelCase  :	List[Any]							  =	[]





 def 				_lowercase(						self	,	A	,	A					)    ->    Union[str, Any]:
        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  :	int							  =	self.__min_dist_top_down_dp(m - 1	,	n - 1					)
               else:
                      UpperCAmelCase  :	Tuple							  =	self.__min_dist_top_down_dp(A	,	n - 1					)
                      UpperCAmelCase  :	str							  =	self.__min_dist_top_down_dp(m - 1	,	A					)
                      UpperCAmelCase  :	List[Any]							  =	self.__min_dist_top_down_dp(m - 1	,	n - 1					)
                      UpperCAmelCase  :	Optional[int]							  =	1 + min(A	,	A	,	A					)

               return self.dp[m][n]





 def 				_lowercase(						self	,	A	,	A					)    ->    List[str]:
        UpperCAmelCase  :	List[Any]							  =	worda
        UpperCAmelCase  :	int							  =	worda
        UpperCAmelCase  :	str							  =	[[-1 for _ in range(len(A					)					)] for _ in range(len(A					)					)]

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






 def 				_lowercase(						self	,	A	,	A					)    ->    int:
        UpperCAmelCase  :	str							  =	worda
        UpperCAmelCase  :	Any							  =	worda
        UpperCAmelCase  :	str							  =	len(A					)
        UpperCAmelCase  :	Tuple							  =	len(A					)
        UpperCAmelCase  :	Union[str, Any]							  =	[[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  :	List[Any]							  =	j
                      elif j == 0:  # second string is empty
                             UpperCAmelCase  :	List[Any]							  =	i
                      elif worda[i - 1] == worda[j - 1]:  # last characters are equal
                             UpperCAmelCase  :	List[Any]							  =	self.dp[i - 1][j - 1]
                      else:
                             UpperCAmelCase  :	int							  =	self.dp[i][j - 1]
                             UpperCAmelCase  :	List[Any]							  =	self.dp[i - 1][j]
                             UpperCAmelCase  :	Union[str, Any]							  =	self.dp[i - 1][j - 1]
                             UpperCAmelCase  :	List[Any]							  =	1 + min(A	,	A	,	A					)
        return self.dp[m][n]


if __name__ == "__main__":
       a     :    Tuple      						=					EditDistance()

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

       a     :    Optional[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 collections.abc import Callable

import numpy as np



def    __lowerCamelCase						(      _lowercase			,       _lowercase			,       _lowercase			,       _lowercase			,       _lowercase	)   ->    np.array:
							UpperCAmelCase  :	Optional[Any]							  =	int(np.ceil((x_end - xa) / step_size	)	)
							UpperCAmelCase  :	str							  =	np.zeros((n + 1,)	)
							UpperCAmelCase  :	Optional[Any]							  =	ya
							UpperCAmelCase  :	Union[str, Any]							  =	xa

							for k in range(_lowercase	):
														UpperCAmelCase  :	Dict							  =	y[k] + step_size * ode_func(_lowercase			,       y[k]	)
														UpperCAmelCase  :	Optional[int]							  =	y[k] + (
														    (step_size / 2) * (ode_func(_lowercase			,       y[k]	) + ode_func(x + step_size			,       _lowercase	))
														)
														x += step_size

							return y


if __name__ == "__main__":
							import doctest

							doctest.testmod()

