Kẻ cướp nhà trong Python

Mỗi nhà có tiền, cướp không thể cướp hai nhà liên tiếp. Tìm tiền tối đa. Ví dụ: [2,7,10,3,1] → 13 (nhà 1,3,5).

Giải pháp

Quy hoạch động:

• prev1 = 0, prev2 = 0.
• Duyệt nums: temp = prev1; prev1 = max(prev2+nums[i], prev1); prev2 = temp.
• Trả về prev1.

Ví dụ

Triển khai Python:

class Solution(object): 
    def rob(self, nums): 
        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]))

Đầu vào

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

Đầu ra

13