[LC] 322. Coin Change

[seungriyou]

https://leetcode.com/problems/coin-change/ similar to #71

Approach

Idea 1 (2D DP)

0/1 knapsack 문제이다. 따라서 2D DP로 접근할 수 있다.

def coinChange(coins: List[int], amount: int) -> int:
    """2D DP"""

    INF = amount + 1

    n = len(coins)

    # dp[i][j]: i번째 coin까지 확인했을 때, j만큼의 amount를 만들 수 있는 동전의 최소 개수
    dp = [[INF] * (amount + 1) for _ in range(n + 1)]
    dp[0][0] = 0

    for i in range(1, n + 1):               # -- 물건 (coins)
        dp[i][0] = 0
        for j in range(1, amount + 1):      # -- 임시 용량 (amount)
            if j >= coins[i - 1]:
                dp[i][j] = min(dp[i - 1][j], dp[i][j - coins[i - 1]] + 1)
            else:
                dp[i][j] = dp[i - 1][j]

    return dp[n][amount] if dp[n][amount] != INF else -1

하지만 dp[i - 1][j], dp[i][j - coins[i - 1]]만 사용하므로, 1D로 optimize 가능하다.

Idea 2 (1D DP)

• bottom-up: dp[k] = k를 만들 수 있는 최소 동전 개수가 되며, 각 entry를 계산할 때마다 모든 coins에 대해 따져보고 최솟값을 택해야 한다.

  이때, 정답은 amount 보다 클 수 없다는 점을 이용하면 INF = amount + 1이라고 설정할 수 있다.

  def coinChange(coins: List[int], amount: int) -> int:
      """
      1D DP (2D DP가 dp[i - 1][j], dp[i][j - coins[i - 1]]만 사용하므로, 1D로 optimize 가능)
      """
  
      INF = amount + 1
  
      dp = [INF] * (amount + 1)
      dp[0] = 0
  
      # for amnt in range(1, amount + 1):
      #     for coin in coins:
      #         if amnt >= coin:
      #             dp[amnt] = min(dp[amnt], dp[amnt - coin] + 1)
  
      for coin in coins:
          for amnt in range(coin, amount + 1):
              dp[amnt] = min(dp[amnt], dp[amnt - coin] + 1)
  
      return dp[amount] if dp[amount] != INF else -1

• top-down: dp(a) = a를 만들 수 있는 최소 동전 개수가 된다. memoization을 사용하기 위해 @lru_cache(None) 혹은 @cache를 이용한다. (ref)

  math.inf + 1 == math.inf 이다!

Idea 3 (BFS) 😮

0 부터 amount 까지의 최단 거리를 구하는 것처럼 접근하면 BFS도 가능하다. (심지어 time 측면에서 DP보다 두 배 이상 좋다...?!)

Complexity

• Time: (DP) O(n * amount)
• Space: (2D DP) O(n * amount) / (1D DP) O(amount)