House Robber

class Solution:
    def rob(self, values: list[int]) -> int:
        n = len(values)
        if n == 0:
            return 0
        if n == 1:
            return values[0]
        
        prev2 = values[0]
        prev1 = max(values[0], values[1])
        
        for i in range(2, n):
            current = max(prev2 + values[i], prev1)
            prev2, prev1 = prev1, current
        
        return prev1

House Robbber II

class Solution:
    def rob(self, values: list[int]) -> int:
        n = len(values)
        if n == 0:
            return 0
        if n == 1:
            return values[0]
        
        option1 = self._rob_linear(values, 0, n - 2)
        option2 = self._rob_linear(values, 1, n - 1)
        return max(option1, option2)
    
    def _rob_linear(self, values: list[int], start: int, end: int) -> int:
        if start == end:
            return values[start]
        
        prev2 = values[start]
        prev1 = max(values[start], values[start + 1])
        
        for i in range(start + 2, end + 1):
            current = max(prev2 + values[i], prev1)
            prev2, prev1 = prev1, current
        
        return prev1

House Robbber III

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def rob(self, root: Optional[TreeNode]) -> int:
        skip, take = self._dfs(root)
        return max(skip, take)
    
    def _dfs(self, node: Optional[TreeNode]) -> tuple[int, int]:
        if not node:
            return (0, 0)
        
        left_skip, left_take = self._dfs(node.left)
        right_skip, right_take = self._dfs(node.right)
        
        # Skip current node: children can be either skipped or taken
        skip_current = max(left_skip, left_take) + max(right_skip, right_take)
        
        # Take current node: children must be skipped
        take_current = node.val + left_skip + right_skip
        
        return (skip_current, take_current)