


from __future__ import annotations

_A									=		'Alexander Joslin'

def 		_UpperCAmelCase							(     SCREAMING_SNAKE_CASE__     :   int							):

     if number <= 0:
          __UpperCamelCase       				=F'n must be greater than 0. Got n = {number}'
          raise ValueError(SCREAMING_SNAKE_CASE__							)

     __UpperCamelCase       				=[number + 1] * (number + 1)

     # starting position
     __UpperCamelCase       				=0
     for i in range(1     ,	SCREAMING_SNAKE_CASE__							):
          __UpperCamelCase       				=min(table[i + 1]     ,	table[i] + 1							)
          # check if out of bounds
          if i * 2 <= number:
               __UpperCamelCase       				=min(table[i * 2]     ,	table[i] + 1							)
          # check if out of bounds
          if i * 3 <= number:
               __UpperCamelCase       				=min(table[i * 3]     ,	table[i] + 1							)
     return table[number]


if __name__ == "__main__":
   import doctest

   doctest.testmod()









def 		_UpperCAmelCase							(     SCREAMING_SNAKE_CASE__     :   Union[str, Any]     ,	SCREAMING_SNAKE_CASE__     :   int							):
     if n < 0:
          return 0
     # table[i] represents the number of ways to get to amount i
     __UpperCamelCase       				=[0] * (n + 1)

     # There is exactly 1 way to get to zero(You pick no coins).
     __UpperCamelCase       				=1

     # Pick all coins one by one and update table[] values
     # after the index greater than or equal to the value of the
     # picked coin
     for coin_val in s:
          for j in range(SCREAMING_SNAKE_CASE__     ,	n + 1							):
               table[j] += table[j - coin_val]

     return table[n]


if __name__ == "__main__":
   import doctest

   doctest.testmod()





