다른 종류의 동전과 총 금액이 있다고 가정합니다. 해당 금액을 구성하는 데 필요한 최소 동전 수를 계산하기 위해 하나의 함수를 정의해야 합니다. 동전의 어떤 조합으로도 해당 금액을 수용할 수 없으면 -1을 반환합니다. 따라서 입력이 [1,2,5]이고 금액이 64이면 출력은 14입니다. 이것은 12*5 + 2 + 2 =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, 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) return dp[amount] ob1 = Solution() print(ob1.coinChange([1,2,5],64))
입력
[1,2,5], 64
출력
14