



'''simple docstring'''





class 	lowerCAmelCase_							:
  '''simple docstring'''




  def __init__(   self				)   ->		Dict:
      lowerCAmelCase__			:  Union[str, Any]											= """"""
      lowerCAmelCase__			:  Optional[int]											= """"""
      lowerCAmelCase__			:  List[Any]											= []




  def 							UpperCAmelCase_     (   self  ,__UpperCAmelCase  ,__UpperCAmelCase				)   ->		int:
      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]:
              lowerCAmelCase__			:  Dict											= self.__min_dist_top_down_dp(m - 1  ,n - 1				)
          else:
              lowerCAmelCase__			:  List[str]											= self.__min_dist_top_down_dp(__UpperCAmelCase  ,n - 1				)
              lowerCAmelCase__			:  List[Any]											= self.__min_dist_top_down_dp(m - 1  ,__UpperCAmelCase				)
              lowerCAmelCase__			:  Tuple											= self.__min_dist_top_down_dp(m - 1  ,n - 1				)
              lowerCAmelCase__			:  Optional[Any]											= 1 + min(__UpperCAmelCase  ,__UpperCAmelCase  ,__UpperCAmelCase				)

          return self.dp[m][n]




  def 							UpperCAmelCase_     (   self  ,__UpperCAmelCase  ,__UpperCAmelCase				)   ->		int:
      lowerCAmelCase__			:  List[Any]											= worda
      lowerCAmelCase__			:  List[str]											= worda
      lowerCAmelCase__			:  List[Any]											= [[-1 for _ in range(len(__UpperCAmelCase				)				)] for _ in range(len(__UpperCAmelCase				)				)]

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






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


if __name__ == "__main__":
 _lowerCAmelCase										=     EditDistance()

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

 _lowerCAmelCase										=     input('''Enter the first string: ''').strip()
 _lowerCAmelCase										=     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'''





def        _SCREAMING_SNAKE_CASE  (	UpperCamelCase							,   UpperCamelCase							,   UpperCamelCase      ):



    """simple docstring"""





    def count_of_possible_combinations(UpperCamelCase      ) -> int:
        if target < 0:
            return 0
        if target == 0:
            return 1
        return sum(count_of_possible_combinations(target - item      ) for item in array      )

    return count_of_possible_combinations(UpperCamelCase      )
def        _SCREAMING_SNAKE_CASE  (	UpperCamelCase							,   UpperCamelCase							,   UpperCamelCase      ):



    """simple docstring"""





    def count_of_possible_combinations_with_dp_array(
        UpperCamelCase							,   UpperCamelCase      ) -> int:
        if target < 0:
            return 0
        if target == 0:
            return 1
        if dp_array[target] != -1:
            return dp_array[target]
        lowerCAmelCase__			:  Any											= sum(
            count_of_possible_combinations_with_dp_array(target - item							,   UpperCamelCase      )
            for item in array      )
        lowerCAmelCase__			:  Tuple											= answer
        return answer

    lowerCAmelCase__			:  Optional[int]											= [-1] * (target + 1)
    return count_of_possible_combinations_with_dp_array(UpperCamelCase							,   UpperCamelCase      )
def        _SCREAMING_SNAKE_CASE  (	UpperCamelCase							,   UpperCamelCase							,   UpperCamelCase      ):



    """simple docstring"""





    lowerCAmelCase__			:  str											= [0] * (target + 1)
    lowerCAmelCase__			:  List[Any]											= 1

    for i in range(1							,   target + 1      ):
        for j in range(UpperCamelCase      ):
            if i - array[j] >= 0:
                dp_array[i] += dp_array[i - array[j]]

    return dp_array[target]


if __name__ == "__main__":
 import doctest

 doctest.testmod()
 _lowerCAmelCase										=     3
 _lowerCAmelCase										=     5
 _lowerCAmelCase										=     [1, 2, 5]
 print(combination_sum_iv(n, array, target))


