322. Coin Change

Medium

Description

給定不同面額的硬幣陣列 coins 和一個目標金額 amount，求湊成該金額所需的最少硬幣數。如果無法湊成，回傳 -1。每種硬幣數量無限。

Example:

Input: coins = [1,2,5], amount = 11 Output: 3

Intuition#

完全背包問題：對每個金額，嘗試每種硬幣，取使用最少硬幣數的方案。

dp[i] = 湊成金額 i 的最少硬幣數
對每種硬幣 c：dp[i] = min(dp[i], dp[i - c] + 1)
初始化 dp[0] = 0，其餘為正無窮

Approaches#

1: Top-Down Memoization#

概念: 遞迴嘗試每種硬幣，記憶化避免重複計算
時間複雜度: O(amount * coins.size)
空間複雜度: O(amount)

class Solution {
    fun coinChange(coins: IntArray, amount: Int): Int {
        val memo = IntArray(amount + 1) { -2 }
        fun dp(rem: Int): Int {
            if (rem == 0) return 0
            if (rem < 0) return -1
            if (memo[rem] != -2) return memo[rem]
            var best = Int.MAX_VALUE
            for (c in coins) {
                val res = dp(rem - c)
                if (res in 0 until best) best = res + 1
            }
            memo[rem] = if (best == Int.MAX_VALUE) -1 else best
            return memo[rem]
        }
        return dp(amount)
    }
}

⭐2: Bottom-Up DP#

概念: 從金額 1 到 amount 依序填表，每次嘗試所有硬幣面額
時間複雜度: O(amount * coins.size)
空間複雜度: O(amount)

class Solution {
    fun coinChange(coins: IntArray, amount: Int): Int {
        val dp = IntArray(amount + 1) { amount + 1 }
        dp[0] = 0
        for (i in 1..amount) {
            for (c in coins) {
                if (c <= i) {
                    dp[i] = minOf(dp[i], dp[i - c] + 1)
                }
            }
        }
        return if (dp[amount] > amount) -1 else dp[amount]
    }
}

🔑 Takeaways#

Pattern: 完全背包 — 每個物品可以無限次使用，求最優解
關鍵技巧: 用 amount + 1 作為「不可達」的初始值，比用 Int.MAX_VALUE 更安全（不會溢位）