LeetCode - Coin Change（找零）

題目描述

給定一個整數數組 coins，其中每個元素代表一種硬幣的面值，以及一個整數 amount，表示總金額。請找出可以用硬幣湊出這個總金額所需的最少硬幣數。如果無法湊出該金額，則返回 -1。

你可以認為每種硬幣的數量是無限的。

範例：

輸入：coins = [1, 2, 5], amount = 11
輸出：3 
解釋：11 = 5 + 5 + 1，所以最少需要 3 枚硬幣。

輸入：coins = [2], amount = 3
輸出：-1

輸入：coins = [1], amount = 0
輸出：0

限制：

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 2^31 - 1
• 0 <= amount <= 10^4

解法思路

這是一道典型的「最小硬幣找零」問題，可以使用動態規劃來解決。構建一個數組 dp，其中 dp[i] 表示湊出金額 i 所需的最少硬幣數。

動態規劃步驟

1. 初始化：建立一個長度為 amount + 1 的數組 dp，初始值為 inf（代表無法達到的金額），其中 dp[0] = 0，表示金額為 0 時不需要硬幣。
2. 遞推公式：對於每個金額 i，遍歷每一種硬幣面值 coin，若 i - coin >= 0，則更新 dp[i] = min(dp[i], dp[i - coin] + 1)，表示用 coin 這枚硬幣可以達成的最少硬幣數。
3. 結果：最終，若 dp[amount] 仍然是初始值，則返回 -1；否則，返回 dp[amount] 的值。

代碼實現

以下是 Python 的實現：

def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for i in range(1, amount + 1):
        for coin in coins:
            if i - coin >= 0:
                dp[i] = min(dp[i], dp[i - coin] + 1)

    return dp[amount] if dp[amount] != float('inf') else -1

代碼解析

1. 初始化 dp 數組：設置長度為 amount + 1 的數組 dp，並初始化為無窮大，dp[0] 為 0。
2. 更新 dp：對於每個金額 i，檢查用每種硬幣 coin 是否可以減少所需硬幣數。
3. 返回結果：若 dp[amount] 無法更新，則說明無法湊出該金額，返回 -1；否則返回 dp[amount]。

時間和空間複雜度

• 時間複雜度：O(amount * n)，其中 n 是硬幣種類數。對於每一個金額，都遍歷 coins。
• 空間複雜度：O(amount)，使用了 dp 數組儲存子問題的解。