題目在這裡。
自己想的答案，bottom up dp不太好想，從top down + cache開始，寫了幾次，每次簡化一點，最終寫成這樣通過OJ。
Python 版本。
class Solution(object):
def coinChange(self, coins, amount):
"""
:type coins: List[int]
:type amount: int
:rtype: int
"""
cache = {0:0}
self.dfs(coins, amount, cache)
return cache[amount]
def dfs(self, coins, amount, cache):
if amount in cache:
return cache[amount]
if amount == 0:
return 0
if amount < 0:
return -1
ans = float('inf')
for coin in coins:
rest_cnt = self.dfs(coins, amount - coin, cache)
if rest_cnt != -1:
ans = min(ans, rest_cnt + 1)
if ans == float('inf'):
cache[amount] = -1
return -1
cache[amount] = ans
return ans 為了更好理解演算法，加了些log，記錄dfs被call了幾次和cache hit，和每個cache key被寫入次數（使用cache和不用cache的情況。
用coins = [1, 2, 5]和amount = 11為例子
用了cache
dfs call: 34
cache hit: 15
key write times
1: 1
2: 1
3: 1
4: 1
5: 1
6: 1
7: 1
8: 1
9: 1
10: 1
11: 1不用cache
dfs call: 928
cache hit: 0
key write times
1: 128
2: 75
3: 44
4: 26
5: 15
6: 9
7: 5
8: 3
9: 2
10: 1
11: 1運行完後cache的內容如下
0: 0
1: 1
2: 1
3: 2
4: 2
5: 1
6: 2
7: 2
8: 3
9: 3
10: 2
11: 3正是從0到11每個amount的最少硬幣數。從此出發，想到bottom up dp正是需要構建如上cache的內容。dp[0] = 0，amount是0，當然一個硬幣不用。dp[amount]就看amount – coin值是不是正，而且之前是否有非-1的值。當算到amount的時候，前面dp[0]到d][amount-coin]都算過了。對所有的coin值都算一遍，把所有dp[amount – coin]的非-1最小值找出來，加1，就是dp[amount]。時間複雜度為O(amount * len(coins))。空間為 O(amount)。
class Solution(object):
def coinChange(self, coins, amount):
"""
:type coins: List[int]
:type amount: int
:rtype: int
"""
dp = [0] * (amount + 1)
for i in range(1, amount + 1):
rest_min_cnt = -1
for coin in coins:
rest = i - coin
if rest >= 0 and dp[rest] != -1:
if rest_min_cnt == -1:
rest_min_cnt = dp[rest]
else:
rest_min_cnt = min(rest_min_cnt, dp[rest])
dp[i] = rest_min_cnt + 1 if rest_min_cnt != -1 else -1
return dp[amount] 過了多日以後自己重新想的Python寫法, 看看是否已經內化並掌握. 對比上面, 做了一些改進, dp list init成全部-1, 代表一開始都不可能. dp[0]設成0, 代表一個coin都不取. 新解法省了rest_min_cnt一個變數.
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];
}
}
