Python에서 변경하는 데 필요한 동전 수를 찾는 프로그램

<시간/>

서로 다른 교단(1,5,10,25)의 동전과 총 금액이 있다고 가정합니다. 해당 금액을 구성하는 데 필요한 최소 동전 수를 계산하기 위해 하나의 함수를 정의해야 합니다. 따라서 입력이 64이면 출력은 7입니다. 이것은 25 + 25 + 10 + 1 + 1 + 1 + 1 =64를 사용하여 구성됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

금액 =0이면 0을 반환
최소 코인 배열> 금액이면 -1 반환
크기가 +1인 dp라는 배열 하나를 정의하고 -1로 채웁니다.
범위에 있는 i의 경우 동전 배열
- i> length of dp – 1이면 다음 부분을 건너뛰고 다음 반복으로 이동합니다.
- dp[i] :=1
- i + 1 범위의 j에 대해
  - dp[j – 1] =-1이면 다음 부분을 건너뛰고 다음 반복으로 이동합니다.
  - 그렇지 않으면 dp[j] =-1이면 dp[j] :=dp[j - i] + 1
  - 그렇지 않으면 dp[j] :=dp[j] 및 dp[j – i] + 1의 최소값
반환 dp[금액]

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

class Solution(object):
   def coinChange(self, amount):
      coins = [1,5,10,25]
      if amount == 0 :
         return 0
      if min(coins) > amount:
         return -1
      dp = [-1 for i in range(0, amount + 1)]
      for i in coins:
         if i > len(dp) - 1:
            continue
         dp[i] = 1
         for j in range(i + 1, amount + 1):
            if dp[j - i] == -1:
               continue
            elif dp[j] == -1:
               dp[j] = dp[j - i] + 1
            else:
               dp[j] = min(dp[j], dp[j - i] + 1)
      return dp[amount]
ob1 = Solution()
print(ob1.coinChange(64))