題目出處
難度
Medium
個人範例程式碼
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
if not coins:
return -1
dp = [float("inf") for _ in range(amount+1)]
dp[0] = 0
for i in range(1, amount+1):
for coin in coins:
if i >= coin and dp[i-coin] != float("inf"):
dp[i] = min(dp[i], dp[i-coin]+1) # last dp add this coin
return -1 if dp[-1] == float("inf") else dp[-1]
最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解
算法說明
完全背包問題可以把公式解開
初始化，全部 INF，多留一個欄位
- dp[0] = 0
- dp[i] = INF (無解的情況，保持原樣)
- dp[i] = min(dp[i], dp[i-可行的目標]+1) (+1 就是代表替換為此目標，例如可以用5元「換一次 [i-5]+1 個五元」的結果)
input handling
如果沒有 coins，return -1，
最後 dp[-1] 即為答案 (如果是保持 INF 不變，那就回傳 -1)
Boundary conditions
用 for 來控制 DP 的範圍