題目出處
難度
Medium
個人範例程式碼
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
if not coins:
return 0
dp = [0] * (amount + 1)
# init
dp[0] = 1
for coin in coins:
for i in range(coin, amount + 1): # start from new coin
dp[i] += dp[i - coin] # function
return dp[-1] # answer
最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解
算法說明
- 此題的前一題為限制使用金幣數量的版本，這題的金幣數量是無限制的。可參考：
https://wongwongnotes-github-io.pages.dev/python/python_leetcode/leetcode-python-322/
這題要處理可以無限使用硬幣，會稍微複雜一些
我們先假設有新的硬幣種類，是一個個出現，從小一路分析到大，
DP 會變成以下的樣子：
# 0 1 2 3 4 5
# 1 0 0 0 0 0 (init)
# 1 1 1 1 1 1 (1)
# 1 1 2 2 3 3 (2)
# 1 1 2 2 3 4 (5)
我們可以推得公式：
- init: 全部 = 0，dp[0] = 1
- function: dp[i] += dp[i-coin] (if i-coin >= 0)
- answer: dp[-1]
常見錯誤 - 處理重複時出錯
這題比較麻煩的是，我們有可能會碰到處理重複時出錯的問題，
例如: (1,2,1) 與 (1,1,2)，其實兩者是同一個意思
因此我們才需要假設「新種類的硬幣，是一個個的出現」。
- 錯誤程式碼範例：
下面的程式碼，因為想要「一次處理好」不同數值下，可以湊出的硬幣總數，
因此碰到了上述所說 (1,2,1) 與 (1,1,2)，其實兩者是同一個意思的問題。
dp = [0 for _ in range(amount+1)]
for i in range(amount+1):
for coin in coins:
if i == coin:
dp[i] += 1
if i - coin >= 0:
dp[i] += dp[i - coin]
return dp[-1]
input handling
如果沒有 coins，return 0，(無組合)
Boundary conditions
用 for 來控制 DP 的範圍