LeetCode 518: Coin Change 2 ·

基本資料
#

難易度: medium 第一次嘗試：2026-08-23 來源：Day 43 learning note

學習脈絡
#

這篇是從 learning note 裡該 LeetCode 題目的段落重新整理出來的版本。我保留當天筆記中的修正點、比較點、容易犯錯的地方，並移除同一天其他非 LeetCode 主題，避免文章內容混題。

筆記中提到的相關提醒
#

LC 518 is the clean unbounded counting anchor.
I do not classify knapsack problems by surface wording alone. I ask three things: can each item be reused, what exactly does dp[...] represent, and what loop direction preserves that meaning in 1D compression. LC 416 is 0/1 reachability so the target loop goes backward. LC 518 is unbounded counting so the amount loop goes forward. LC 322 is also unbounded, but its state is minimum coins, so the recurrence and invalid-state handling are different.
explain LC 518 as unbounded counting with forward loop direction
explain why LC 322 is a different answer shape from LC 518

當天筆記摘錄
#

Problem 2 - LC 518 Coin Change 2
#

Pattern: unbounded knapsack counting combinations

Why This Fits
#

Each coin can be reused:

any number of times

The question is:

how many combinations make the amount?

Core State / Invariant
#

dp[a] = number of combinations to make amount a using the coins processed so far

Base Case
#

dp[0] = 1

Reason:

there is exactly one way to make amount 0: choose no coins

Transition
#

For each coin:

dp[a] += dp[a - coin]

when:

a >= coin

Why Loop Direction Matters
#

Iterate amount forward:

for a from coin up to amount

Reason:

forward iteration lets the current coin be reused in the same coin round

Complexity
#

Time: O(len(coins) * amount)
Space: O(amount)

Common Mistakes
#

iterating amount backward and accidentally enforcing 0/1
putting amount as the outer loop and counting permutations instead of combinations
saying dp[a] is minimum coins instead of number of ways
forgetting why dp[0] = 1

Strong Spoken Explanation
#

I define dp[a] as the number of combinations to make amount a using the coins processed so far. The base case is dp[0] = 1, because there is exactly one way to make amount zero: choose nothing. For each coin, I iterate amounts forward so the same coin can be reused in the same round. The transition is dp[a] += dp[a - coin]. Keeping coins as the outer loop makes the answer combinations rather than permutations.

正確解法
#

上面的筆記保留了推理脈絡和當天需要修正的點。下面是我會提交的版本。

from typing import List

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp = [0] * (amount + 1)
        dp[0] = 1

        for coin in coins:
            for a in range(coin, amount + 1):
                dp[a] += dp[a - coin]

        return dp[amount]