LeetCode #198 House Robber: DP บ้านคู่กันห้ามปล้น — จากอาร์เรย์สู่ตัวแปรสองตัว

House Robber ให้ลิสต์เงินในแต่ละบ้าน — ปล้นบ้านติดกันไม่ได้ หาผลรวมมากสุดครับ

วิธี 1: DP อาร์เรย์ O(n)

dp[i] = max(dp[i-1], dp[i-2] + nums[i]) ชัดกับนิยาม ดีตอนอธิบายบอร์ด

วิธี 2: เหลือตัวแปรสองตัว

จำแค่ prev / curr พื้นที่ O(1) — คำตอบที่สัมภาษณ์ชอบ

วิธี 3: recursion + memo

ถูกแต่ช้าและกินสแต็กถ้าไม่ระวัง — ใช้สอน overlap ของ subproblem มากกว่าโปรดักชัน

import unittest

def rob(nums: list[int]) -> int:
    prev = curr = 0
    for value in nums:
        prev, curr = curr, max(curr, prev + value)
    return curr

class HouseRobberTests(unittest.TestCase):
    def test_examples(self):
        self.assertEqual(rob([1, 2, 3, 1]), 4)
        self.assertEqual(rob([2, 7, 9, 3, 1]), 12)
        self.assertEqual(rob([]), 0)

if __name__ == "__main__":
    unittest.main()

เลือก rolling variables เป็นค่าเริ่มต้นเมื่อ n ใหญ่และโจทย์ไม่ถามเส้นทางบ้าน

Recap

• วาดตาราง dp สองสามหลังก่อนย่อตัวแปร
• เทสต์เคสว่าง / บ้านเดียว / สองบ้าน
• อย่าสับสนกับ House Robber II (วงกลม)