Problem :

https://leetcode.com/problems/coin-change/


My Solution :

class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
targets = [amount]
visited = set()
count = 0
while targets:
if 0 in targets:
return count
level_targets = set()
for target in targets:
for coin in coins:
remain = target - coin
if remain == 0:
return count + 1
if remain > 0 and remain not in visited:
level_targets.add(remain)
visited.add(remain)
targets = level_targets
count += 1
return -1


Comment :

amount를 만들어낼 수 있는 동전 조합의 최소 갯수를 구해야 하기 때문에 가장 먼저 떠올랐던 방법이 BFS이다. 중복 탐색은 visited라는 set을 활용하여 배제하였다.


아래는 bottom up 방식의 DP 접근법


My Solution 2 :

class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
MAX = amount + 1
dp = [0] + [MAX]*amount
for i in range(1, amount+1):
dp[i] = 1 + min(
dp[i-coin] if coin <= i else MAX for coin in coins)
return dp[-1] if dp[-1] < MAX else -1