作为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]