On this page

ข้อ 61 · LC198 House Robber (ขโมยบ้าน) 🟡

👋 อ่านฟรีทั้งหมดบน Aph's Blog — เนื้อหาภาษาไทย ทำตามทีละหน้าใน sidebar ได้เลย หากมีข้อเสนอแนะหรืออยากให้เพิ่มหัวข้อไหน บอกได้เสมอ

choose ขโมยบ้านให้ได้เงิน maximum โดยห้ามขโมยสองหลัง adjacent (ติดกัน) ด้วย DP แบบ take/skip

โจทย์ (LC198): วางแผนขโมยบ้านที่เรียงกันเป็นแถว แต่ละหลังมีเงินสดเก็บอยู่จำนวนหนึ่ง ข้อจำกัดเดียวคือบ้านที่ adjacent (ติดกัน) มีระบบรักษาความปลอดภัยเชื่อมถึงกัน ถ้าขโมยสองหลังที่ adjacent ในคืนเดียวกัน ระบบจะแจ้งตำรวจโดยอัตโนมัติ กำหนด array จำนวนเต็ม nums ซึ่ง nums[i] คือเงินสดในบ้านหลังที่ i มา ให้หาจำนวนเงิน maximum ที่ขโมยได้โดยไม่โดนแจ้งเตือน

Example 1

Input:: nums = [1, 2, 3, 1]
Output:: 4
Explanation:: ขโมยหลัง index 0 (เงิน 1) และหลัง index 2 (เงิน 3) รวม 1 + 3 = 4

Example 2

Input:: nums = [2, 7, 9, 3, 1]
Output:: 12
Explanation:: ขโมยหลัง index 0 (เงิน 2), index 2 (เงิน 9) และ index 4 (เงิน 1) รวม 2 + 9 + 1 = 12

Example 3

Input:: nums = [2, 1, 1, 2]
Output:: 4
Explanation:: ขโมยหลังแรกกับหลังสุดท้าย (เว้นสองหลังตรงกลาง) ได้ 2 + 2 = 4

Constraints (ข้อจำกัด)

1 <= nums.length <= 100
0 <= nums[i] <= 400

แนวทาง — ต้องใช้อะไร & คิดยังไง

โจทย์นี้เป็น DP 1 มิติแบบ take/skip (เลือก/ไม่เลือก) คลาสสิก ที่บ้านหลังที่ i เรามีสอง choice: skip (ไม่ขโมย, คำตอบเท่ากับถึงหลัง i-1) หรือ take (ขโมย, ได้ nums[i] บวกคำตอบถึงหลัง i-2 เพราะต้องข้ามหลังที่ adjacent) เลือกทางที่ได้เงินมากกว่า

state คือ dp[i] = เงิน maximum เมื่อพิจารณาถึงบ้านหลังที่ i และ transition คือ dp[i] = max(dp[i-1], dp[i-2] + nums[i]) เพราะ dp[i] depend on แค่ dp[i-1] กับ dp[i-2] เราจึงยุบ table เหลือสอง variable prev กับ curr แล้ว rotate ไปข้างหน้าได้เลย

initialize prev = 0 (เงิน maximum ถึงบ้านก่อนหน้า) และ curr = 0 (เงิน maximum ถึงบ้านปัจจุบัน)
iterate แต่ละหลัง money ใน nums
compute ค่าใหม่: skip (curr) เทียบกับ take (prev + money) เลือกตัวมากกว่า
rotate ค่าด้วย prev, curr = curr, max(curr, prev + money)
return curr

จุดพลาดที่พบบ่อย

อย่าคิดว่าต้องขโมยเว้นบ้านสลับกันตายตัว จริง ๆ แค่ห้าม adjacent เท่านั้น เช่น [2,1,1,2] คำตอบที่ดีที่สุดคือขโมยหลังแรกกับหลังสุดท้าย (2+2 = 4) ซึ่งเว้นสองหลัง max transition จัดการกรณีนี้ให้อัตโนมัติ ไม่ต้องเขียนเงื่อนไขพิเศษ

ไล่ทีละสเต็ป

ไล่ nums = [2,7,9,3,1] ดูค่า prev กับ curr rotate ไป:

money	prev + money	curr ใหม่ = max	prev, curr หลัง rotate
2	0+2 = 2	max(0,2) = 2	prev=0, curr=2
7	0+7 = 7	max(2,7) = 7	prev=2, curr=7
9	2+9 = 11	max(7,11) = 11	prev=7, curr=11
3	7+3 = 10	max(11,10) = 11	prev=11, curr=11
1	11+1 = 12	max(11,12) = 12	prev=11, curr=12 ← คำตอบ

▶ เฉลยละเอียด (ลองเองก่อนนะ)

เฉลย (Python) — โค้ดนี้รันได้จริงpython

def rob(nums):
    # prev = เงินมากสุดถึงบ้านก่อนหน้า, curr = เงินมากสุดถึงบ้านปัจจุบัน
    prev, curr = 0, 0
    for money in nums:
        # ไม่ขโมยหลังนี้ (curr) เทียบกับ ขโมยหลังนี้ (prev + money)
        prev, curr = curr, max(curr, prev + money)
    return curr

print(rob([1, 2, 3, 1]))     # 4
print(rob([2, 7, 9, 3, 1]))  # 12

Output

4
12

transition คือ dp[i] = max(dp[i-1], dp[i-2] + nums[i]) ความหมายคือ ที่บ้านหลังนี้เรามีสอง choice: skip (คำตอบเท่าเดิมกับ dp[i-1]) หรือ take (ต้องข้ามหลัง adjacent จึงต่อยอดจาก dp[i-2] แล้ว sum เงินหลังนี้) เพราะ depend on แค่สองค่าก่อนหน้า เราจึงแทน dp[i-2] ด้วย prev และ dp[i-1] ด้วย curr

จุดสำคัญของการ rotate คือ prev, curr = curr, max(curr, prev + money) ทำพร้อมกันในบรรทัดเดียว: prev ตัวใหม่ต้องเป็น curr ตัวเก่า ส่วน curr ตัวใหม่ compute จาก curr และ prev ตัวเก่า ถ้าแยกบรรทัดจะ overwrite กันเอง initialize ด้วย 0 ทั้งคู่ครอบคลุมกรณี nums ว่างและหลังแรกได้พอดี

Time O(n) iterate ครั้งเดียว · Space O(1) ใช้สอง variable แทน table

💡 สรุป pattern

โจทย์ take/skip โดยมี constraint (ข้อจำกัด) ห้ามเลือกของที่ adjacent ให้ตั้ง dp[i] = max(skip dp[i-1], take dp[i-2] + ค่าปัจจุบัน) แล้วยุบเหลือสอง variable — pattern นี้ต่อยอดไปโจทย์ House Robber II และอื่น ๆ ได้