題目

  • 題目連結
  • 目標函式 : coinChange(coins, amount)
    • Input : coins: List[int]、amount: int
    • Output : int

解題概念

  • 題意 : 給定一整數陣列 coins 代表不同面額的硬幣，並且 amount 代表總金額
    • 回傳組成 amount 所需的最少硬幣數量
    • 若該金額不能由任何硬幣組成，則回傳 -1

我的寫法

  • 想法 :
    1. 先將 coins 升序排序
    2. 對 coins 反轉並使用 for 迴圈
      • 若 amount 可以除以 coins[i]，則更新 cnt 與 amount
      • 當面對 coins[i] == 1 時，再做特殊處理
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    def coinChange(self, coins, amount):
        
        coins.sort()
        if not amount: return 0
        cnt = 0
        for coin in coins[::-1]:
            if coin == 1:
                cnt += amount
                amount = 0
                break

            if amount >= coin:
                cnt += amount // coin
                amount = amount % coin
            
        return cnt if amount == 0 else -1
  • 成效 :
    • Time Complexity : Wrong Answer
    • 發現問題 : 這種計算方式並不是最佳解
      • 如果遇到 coins = [1, 2, 8, 9]、amount = 16 時 :
        • 我的算法會變成 9 + 2 + 2 + 2 + 1 = 16 (回傳 5)
        • 但最佳解應為 8 + 8 = 16 (回傳 2)

解答 or 其他優秀寫法 - Dynamic Programming

  • 想法 : 應該使用 Dynamic Programming
    • 使用 dp[0] ~ dp[amount] 去紀錄從 0 到 amount 的最佳解
    • 然後使用雙重迴圈 : 先針對每個可能 amount 的值 i，再針對每個 coin
    • 若 i 比 coin 大，即更新 dp[i] (決定計不計算 coin，再取較小值 min(dp[i], dp[i - coin] + 1))
    • 若最後發現 dp[amount] == max_value，代表 amount 無解，則回傳 -1
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    def coinChange(self, coins, amount):
        
        max_value = amount + 1
        dp = [max_value] * max_value
        dp[0] = 0

        for i in xrange(1, max_value):
            for coin in coins:
                if i >= coin: 
                    dp[i] = min(dp[i], dp[i - coin] + 1)

        if dp[amount] == max_value:
            return -1
        return dp[amount]
  • 成效 :
    • Time Complexity : $O(n\times \text{amount})$
    • Runtime: 714 ms (faster than 82.91%)
    • Memory Usage: 13.5 MB (more than 98.52%)