





class        _a    :

      """simple docstring"""


      def __init__(		self:			str					):
          '''simple docstring'''


          UpperCamelCase__:	str					=     ''
          UpperCamelCase__:	Any					=     ''
          UpperCamelCase__:	List[Any]					=     []






      def 			UpperCAmelCase_       (		self:			Tuple	,    __lowerCamelCase:			int	,    __lowerCamelCase:			int					):
          '''simple docstring'''


          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__:	List[Any]					=     self.__min_dist_top_down_dp(m - 1	,    n - 1					)
              else:
                  UpperCamelCase__:	Any					=     self.__min_dist_top_down_dp(_a	,    n - 1					)
                  UpperCamelCase__:	Optional[Any]					=     self.__min_dist_top_down_dp(m - 1	,    _a					)
                  UpperCamelCase__:	List[Any]					=     self.__min_dist_top_down_dp(m - 1	,    n - 1					)
                  UpperCamelCase__:	int					=     1 + min(_a	,    _a	,    _a					)

              return self.dp[m][n]






      def 			UpperCAmelCase_       (		self:			Optional[int]	,    __lowerCamelCase:			str	,    __lowerCamelCase:			str					):
          '''simple docstring'''


          UpperCamelCase__:	List[Any]					=     worda
          UpperCamelCase__:	List[Any]					=     worda
          UpperCamelCase__:	List[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 			UpperCAmelCase_       (		self:			int	,    __lowerCamelCase:			str	,    __lowerCamelCase:			str					):
          '''simple docstring'''


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


if __name__ == "__main__":
   A__:    List[Any]  	=	EditDistance()

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

   A__:    Optional[Any]  	=	input('''Enter the first string: ''').strip()
   A__:    Optional[Any]  	=	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'''





import functools

def 			a_	(				_lowerCAmelCase			,_lowerCAmelCase			) -> int:

  # Validation
  if not isinstance(_lowerCAmelCase			,_lowerCAmelCase			) or not all(isinstance(_lowerCAmelCase			,_lowerCAmelCase			) for day in days			):
    raise ValueError('The parameter days should be a list of integers'			)

  if len(_lowerCAmelCase			) != 3 or not all(isinstance(_lowerCAmelCase			,_lowerCAmelCase			) for cost in costs			):
    raise ValueError('The parameter costs should be a list of three integers'			)

  if len(_lowerCAmelCase			) == 0:
    return 0

  if min(_lowerCAmelCase			) <= 0:
    raise ValueError('All days elements should be greater than 0'			)

  if max(_lowerCAmelCase			) >= 366:
    raise ValueError('All days elements should be less than 366'			)

  __lowerCamelCase			:			int       			=					set(_lowerCAmelCase			)

  @functools.cache
  def dynamic_programming(_lowerCAmelCase			) -> int:
    if index > 365:
      return 0

    if index not in days_set:
      return dynamic_programming(index + 1			)

    return min(
        costs[0] + dynamic_programming(index + 1			)			,costs[1] + dynamic_programming(index + 7			)			,costs[2] + dynamic_programming(index + 30			)			,)

  return dynamic_programming(1			)


if __name__ == "__main__":
   import doctest

   doctest.testmod()






