파이썬에서 동전 교환

다른 종류의 동전과 총 금액이 있다고 가정합니다. 해당 금액을 구성하는 데 필요한 최소 동전 수를 계산하기 위해 하나의 함수를 정의해야 합니다. 동전의 어떤 조합으로도 해당 금액을 수용할 수 없으면 -1을 반환합니다. 따라서 입력이 [1,2,5]이고 금액이 11이면 출력은 3입니다. 이것은 5 + 5 + 1 =11을 사용하여 구성됩니다.

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

금액 =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, coins, amount):
      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)
         #print(dp)
      return dp[amount]
ob1 = Solution()
print(ob1.coinChange([1,2,5], 11))

입력

[1,2,5]
11