Leetcode # 518. Coin Change II

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

Solution: Top-Down DP

用 (amount, len(coins)) 作為 self.memo 的key

Time Complexity: O(n * amount)
Space Complexity: O(n * amount)
1 <= coins[i] <= 5000
n := len(coins)
time/space complexity = O(n * (amount / 1)) = O(n * amount)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def __init__(self):
    self.memo = {}
  def change(self, amount: int, coins: List[int]) -> int:
    if not coins: return 1 if amount == 0 else 0
    n = len(coins)
    if (amount, n) not in self.memo: 
      _amount = amount
      remained_coins = coins[:-1]
      self.memo[amount, n] = self.change(_amount, remained_coins)
      while _amount >= coins[-1]:
        self.memo[amount, n] += \
            self.change(_amount := _amount - coins[-1], remained_coins)
    return self.memo[amount, n]

Solution: Bottom DP, Optimized Space Complexity

用 (amount, len(coins)) 作為 self.memo 的key

Time Complexity: O(n * amount)
Space Complexity: O(n * amount)O(amount)
(The input and output generally do not count towards the space complexity.)

class Solution:
  def change(self, amount: int, coins: List[int]) -> int:
    if amount == 0: return 1
    prev_dp, result = collections.Counter([amount]), 0
    for i, coin in enumerate(coins):
      if i == len(coins) - 1:
        result += sum([prev_dp[remained] \
                       for remained in prev_dp if remained % coin == 0])
        break
      curr_dp = prev_dp.copy()
      for remained in prev_dp:
        _remained = remained
        while _remained >= coin:
          _remained -= coin
          if _remained == 0: 
            result += prev_dp[remained]
          else:
            curr_dp[_remained] += prev_dp[remained]
      prev_dp = curr_dp
    return result

More Concise Code

Ex: coins = [1, 2]

class Solution:
  def change(self, amount: int, coins: List[int]) -> int:
    dp = [1] + [0] * amount
    for coin in coins:
      for _amount in range(coin, amount + 1):
        dp[_amount] += dp[_amount - coin]
    return dp[amount]

Last Updated on 2023/08/16 by A1go