โจรขโมยบ้านใน Python

สมมติว่ามีเมืองหนึ่ง และแต่ละหลังคาบ้านในเมืองมีเงินจำนวนหนึ่ง โจรหนึ่งคนต้องการขโมยเงินในคืนเดียว เมืองมีระบบความปลอดภัย คือ ถ้าบ้านติดกันสองหลังถูกขโมยในคืนเดียวกัน จะโทรแจ้งตำรวจอัตโนมัติ เราต้องหาว่าโจรสามารถขโมยได้สูงสุดเท่าไหร่

มีอาร์เรย์หนึ่ง ที่ดัชนี i, A[i] คือจำนวนเงินในบ้านที่ i สมมติอาร์เรย์เป็น A = [2, 7, 10, 3, 1] ผลลัพธ์จะเป็น 13 ค่าสูงสุดคือเอาจากบ้าน1 (ค่า 2), บ้าน3 (ค่า 10), และบ้าน5 (ค่า 1) รวมเป็น 13

วิธีการแก้ปัญหา

• ตั้งค่า prev1 := 0 และ prev2 = 0
• สำหรับ i = 0 ถึงความยาวของ A - 1:
  • temp := prev1
  • prev1 := ค่าสูงสุดของ prev2 + A[i] และ prev1
  • prev2 = temp
• คืนค่า prev1

ตัวอย่าง

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        prev2 = 0
        prev1 = 0
        for i in range(0, len(nums)):
            temp = prev1
            prev1 = max(prev2 + nums[i], prev1)
            prev2 = temp
        return prev1

ob1 = Solution()
print(ob1.rob([2,7,10,3,1]))

อินพุต

nums = [2,7,10,3,1]

เอาต์พุต

13