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
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]
class Solution(object):
def coinChange(self, coins, amount):
"""
:type coins: List[int]
:type amount: int
:rtype: int
"""
dp = [-1] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for j in coins:
k = i - j
if k >= 0 and dp[k] != -1:
if dp[i] == -1:
dp[i] = dp[k] + 1
else:
dp[i] = min(dp[i], dp[k] + 1)
return dp[amount]
Java版本的bottom up dp解法
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
for (int i = 1; i <= amount; i++) {
int restMinCoins = -1;
for (int coin : coins) {
int remainder = i - coin;
if (remainder >= 0 && dp[remainder] != -1) {
if (restMinCoins == -1) {
restMinCoins = dp[remainder];
} else {
restMinCoins = Math.min(restMinCoins, dp[remainder]);
}
}
}
if (restMinCoins == -1) {
dp[i] = -1;
} else {
dp[i] = restMinCoins + 1;
}
}
return dp[amount];
}
}
