硬幣找零問題（coin-change problem）

給你一組硬幣面額（比方說 1、3、4）與一個目標金額，每種硬幣供應無限。問題有兩種常見版本：湊出恰好等於該金額所需的最少硬幣數，以及（計數版本）你能用多少種相異的方式湊出該金額。兩者都有日常的味道——收銀員找零——但令人意外的是，「總是抓裝得下的最大硬幣」這個直觀的貪婪策略，對於任意面額的最小化版本可能給出錯誤答案。

對最少硬幣版本，令 dp[x] 為湊出金額 x 的最少硬幣數。轉移把每種硬幣當作最後用的硬幣來試：dp[x] = 1 + 在 c <= x 的硬幣 c 中取 dp[x - c] 的最小值。基底情況是 dp[0] = 0（零枚硬幣湊出零），其餘每個 dp[x] 都起始為無窮大，使你湊不出的金額維持無窮大。依遞增順序填 dp[0], dp[1], ..., dp[amount]，花 O(金額乘以硬幣種數) 時間。對計數版本，令 ways[x] 為湊出 x 的方式數；你一次處理一種硬幣，對每種硬幣 c，讓 x 從 c 往上，更新 ways[x] += ways[x - c]——硬幣放外層迴圈、金額放內層，正是讓每個組合只被算一次而非算進排列順序的關鍵。

硬幣找零是看清「貪婪不是證明」的經典場合。用美國硬幣（1、5、10、25）時貪婪恰好最佳，這讓人放心去信任它；但用像 1、3、4 的面額、目標 6 時，貪婪拿 4 再拿 1 再拿 1（三枚），而最佳是 3 + 3（兩枚）——動態規劃會找出貪婪錯過的兩枚答案。還有兩個誠實的點：和 0/1 背包一樣，O(金額乘以硬幣) 的執行時間是偽多項式（金額相對於其位元長度是指數的），而最少硬幣與計數方式這兩個版本是真正不同的動態規劃，其迴圈結構不可互換，因為在計數版本中把迴圈巢狀搞錯，會無聲地把同一組合按不同順序算了好幾次。