作為lc322 coin change的follow up，leetcode標記為medium，而且acceptance rate為47%，高於coin change的34.2%。個人做下來覺得很難，比322要難。寫出一個邏輯正確的解法還算OK，但是OJ會超時。
Python 版本 top down dfs + backtrace
class Solution(object):
def change(self, amount, coins):
"""
:type amount: int
:type coins: List[int]
:rtype: int
"""
cur_path = []
paths = set()
self.dfs(amount, coins, cur_path, paths)
return len(paths)
def dfs(self, amount, coins, cur_path, paths):
if amount == 0:
path = tuple(sorted(cur_path))
paths.add(path)
return
if amount < 0:
return
for coin in coins:
cur_path.append(coin)
self.dfs(amount - coin, coins, cur_path, paths)
del cur_path[-1]
Python 版本 bottom up dp
class Solution(object):
def change(self, amount, coins):
"""
:type amount: int
:type coins: List[int]
:rtype: int
"""
dp = [None] * (amount + 1)
dp[0] = set()
dp[0].add(())
for i in range(1, amount + 1):
combos = set()
for coin in coins:
rest = i - coin
if rest >= 0 and dp[rest] is not None:
for rest_combo in dp[rest]:
combo = tuple(sorted(rest_combo + (coin,)))
combos.add(combo)
if len(combos) > 0:
dp[i] = combos
return len(dp[amount]) if dp[amount] is not None else 0 以上兩種都超時。
實在想不到能過OJ的算法，以下dp算法也是我從網上大神們那學到了。盯着看了2天才算想明白了其中道理。寫得非常簡短。
class Solution(object):
def change(self, amount, coins):
"""
:type amount: int
:type coins: List[int]
:rtype: int
"""
dp = [1] + [0] * amount
for coin in coins:
for i in xrange(amount - coin + 1):
if dp[i]:
dp[i + coin] += dp[i]
return dp[amount]