LeetCode #322 Coin Change: แลกเหรียญให้น้อยสุดด้วย DP

เคยยืนที่ตู้กดน้ำ แล้วอยากทอนเงินด้วยเหรียญให้น้อยชิ้นที่สุดไหม โจทย์ coin-change ให้ชุดมูลค่าเหรียญและยอด amount แล้วหาจำนวนเหรียญน้อยสุดที่รวมได้พอดี ถ้าทำไม่ได้ให้ตอบ -1 เหรียญแต่ละชนิดใช้กี่ครั้งก็ได้

วิธีที่ 1: greedy หยิบเหรียญใหญ่ก่อน

เรียงเหรียญจากมากไปน้อยแล้วหยิบทีละเหรียญที่ใหญ่สุดที่ยังไม่เกินยอด เวลาประมาณ O(k log k + k) ตามชนิดเหรียญ ข้อดีคือสั้นและถูกกับเหรียญมาตรฐานบางระบบ ข้อเสียใหญ่: ไม่ถูกต้องทั่วไป เช่น coins = [1, 3, 4], amount = 6 greedy ได้ 4+1+1 (3 เหรียญ) แต่คำตอบจริงคือ 3+3 (2 เหรียญ)

วิธีที่ 2: BFS ตามจำนวนเหรียญ

มองแต่ละยอดเงินเป็นโหนด เริ่มจาก 0 แล้วขยายด้วยการบวกเหรียญทีละชนิด ชั้นของ BFS คือจำนวนเหรียญที่ใช้ เมื่อถึง amount ครั้งแรกได้คำตอบน้อยสุด เวลา O(amount × k) พื้นที่ O(amount) เหมาะเมื่ออยากคิดเป็น shortest path และตัดยอดซ้ำด้วย visited set

วิธีที่ 3: bottom-up DP (แนะนำหลัก)

ให้ dp[x] = จำนวนเหรียญน้อยสุดที่ทำยอด x ได้ ตั้ง dp[0] = 0 และค่าอื่นเป็น infinity แล้วสำหรับทุกยอด x ลองทุกเหรียญ c อัปเดต dp[x] = min(dp[x], dp[x - c] + 1) เมื่อ x >= c เวลา O(amount × k) พื้นที่ O(amount) หากจบแล้วยัง infinity แปลว่าแลกไม่ได้ ให้คืน -1

Invariant: หลังประมวลผลถึง x ค่า dp[x] เป็นคำตอบที่ถูกต้องของย่อยนั้นแล้ว จึงสร้างคำตอบใหญ่จากคำตอบเล็กได้อย่างปลอดภัย

วิธีที่ 4: top-down memoization

เขียนฟังก์ชัน f(remain) ที่ลองลดทุกเหรียญแล้วเก็บผลใน memo Base เป็น 0 → 0 และติดลบเป็นเป็นไปไม่ได้ เวลา/พื้นที่เทียบเท่า bottom-up แต่ recursion ลึกอาจชน limit ใน Python เมื่อ amount ใหญ่ ควรใช้เมื่ออยากอ่านโค้ดแบบ “ถามยอดที่เหลือ”

def coin_change(coins, amount):
    INF = amount + 1
    dp = [0] + [INF] * amount
    for x in range(1, amount + 1):
        for c in coins:
            if c <= x:
                dp[x] = min(dp[x], dp[x - c] + 1)
    return -1 if dp[amount] == INF else dp[amount]


samples = [
    ([1, 2, 5], 11, 3),
    ([2], 3, -1),
    ([1], 0, 0),
    ([1, 3, 4], 6, 2),
    ([2, 5, 10, 1], 27, 4),
]
for coins, amount, expected in samples:
    got = coin_change(coins, amount)
    assert got == expected, (coins, amount, got, expected)
print("ok", len(samples), "cases")

เลือกตามสถานการณ์

สถานการณ์	วิธีที่เหมาะ	เหตุผลสั้นๆ
เหรียญ canonical ที่พิสูจน์แล้วว่า greedy ถูก	greedy	เร็วและโค้ดสั้น
มองเป็นระยะทางสั้นสุด	BFS	ได้คำตอบแรกคือจำนวนน้อยสุด
สัมภาษณ์ / ใช้ทั่วไป	bottom-up DP	ถูกต้องเสมอใน O(amount × k)
อ่านจากยอดที่เหลือลงมา	top-down memo	โครงใกล้คำถามโจทย์

เคสที่ต้องเช็ก: amount = 0 ตอบ 0, เหรียญใหญ่กว่ายอดทั้งหมด, มีเหรียญ 1 หรือไม่มี, และชุดที่ greedy พลาดอย่าง [1, 3, 4] อย่าคืน 0 เมื่อแลกไม่ได้ — โจทย์ต้องการ -1

Recap

• อย่าเชื่อ greedy จนกว่าจะพิสูจน์ระบบเหรียญ
• ตั้ง dp[0] = 0 แล้วเติมทุกยอดด้วยเหรียญทุกชนิด
• ถ้าค่าสุดท้ายยัง infinity ให้ตอบ -1
• เทียบกับ BFS หรือ brute บน amount เล็กก่อนเชื่อ
• default เลือก bottom-up DP ครับ