[LeetCode] #518. Coin Change 2
題目
You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.
Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0.
You may assume that you have an infinite number of each kind of coin.
The answer is guaranteed to fit into a signed 32-bit integer.
直覺解
構想：
像 70. Climbing Stairs 那樣，amount 對應到樓梯總共有幾階，coins 對應到不同的 step。
python 3 實作（失敗）：
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
return self.coin_change(0, amount, coins)
def coin_change(self, curr, amount, coins):
if curr > amount:
return 0
if curr == amount:
return 1
result = []
for coin in coins:
result.append(self.coin_change(curr + coin, amount, coins))
return sum(result)
執行結果：
Wrong Answer
Input:
5
[1, 2, 5]
Output: 9
Expected: 4
錯誤發生原因：
- 題目不在乎兌換的順序。但我的寫法，相同的硬幣兌換數量，會因為兌換順序不同而被重複計算。例如，同樣都是「把 5 塊換成 2 個 2 塊和 1 個 1 塊」，但是兌換順序有好幾種，例如「1 + 2 + 2」、「2 + 1 + 2」、「2 + 2 + 1」。
構想：
兌換過程中，如果已經開始兌換面額比較小的硬幣，就不能再兌換面額大的硬幣。例如，總共有 1, 2, 5 三種面額的硬幣，如果一開始就兌換了一個面額 1 的硬幣，之後就只能兌換 面額 ≤ 1 的硬幣。這樣的話，「把 5 塊換成 2 個 2 塊和 1 個 1 塊」就只會有一種兌換順序「2 + 2 + 1」，就能避免重複計算的問題。
自己的 python 3 實作（失敗）：
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
coins.sort(reverse=True)
coin_num = {}
for coin in coins:
coin_num[coin] = 0
return self.coin_change(0, coin_num, amount, coins)
def coin_change(self, curr, coin_num, amount, coins):
if curr > amount:
return 0
if curr == amount:
return 1
star = 0
for coin, num in coin_num.items():
if num != 0:
star = coins.index(coin)
result = []
for index, coin in enumerate(coins[star:]):
coin_num_update = coin_num.copy()
coin_num_update[coin] += 1
result.append(self.coin_change(curr + coin, coin_num_update, amount, coins))
return sum(result)
執行結果：
Time Limit Exceeded
Last executed input:
500
[3,5,7,8,9,10,11]
構想：
加上快取機制，看能不能加快計算速度
自己的 python 3 實作（失敗）：
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
coins.sort(reverse=True)
cache = {}
coin_num = {}
for coin in coins:
coin_num[coin] = 0
return self.coin_change(0, coin_num, amount, coins, cache)
def coin_change(self, curr, coin_num, amount, coins, cache):
if curr > amount:
return 0
if curr == amount:
return 1
tag = '#'.join([str(item) for item in coin_num.values()])
if cache.get(tag) is None:
star = 0
for coin, num in coin_num.items():
if num != 0:
star = coins.index(coin)
result = []
for index, coin in enumerate(coins[star:]):
coin_num_update = coin_num.copy()
coin_num_update[coin] += 1
result.append(self.coin_change(curr + coin, coin_num_update, amount, coins, cache))
cache[tag] = sum(result)
return cache[tag]
執行結果：
Time Limit Exceeded
Last executed input:
500
[3,5,7,8,9,10,11]
研究別人的解
來源：Python sol by DP in bottom-up 85%+ [w/ Visualization]
別人的 python 3 實作：
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
# base case:
# amount 0's method count = 1 (by taking no coins)
change_method_count = [1] + [ 0 for _ in range(amount)]
# make change with current coin, from small coin to large coin
for cur_coin in coins:
# update change method count from small amount to large amount
for small_amount in range(cur_coin, amount+1):
nbsp; # current small amount can make changed with current coin
nbsp; change_method_count[small_amount] += change_method_count[small_amount - cur_coin]
return change_method_count[amount]
效能：
Runtime: 132 ms, faster than 95.97% of Python3 online submissions for Coin Change 2.
Memory Usage: 14.5 MB, less than 67.61% of Python3 online submissions for Coin Change 2.
Comments
Post a Comment