[LeetCode][Python3] 322. Coin Change

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