Solutions

# At each house, we can either rob it and add its amount to the maximum amount from two houses back, or skip it and take the maximum amount from the previous house. This leads to a recursive relation: dp[i] = max(dp[i-1], nums[i] + dp[i-2]). We can implement this using either recursion with memoization or iterative dynamic programming.
# dp

# Iterative bottom-up dp - O(n) time, O(n) space
def rob(nums: list[int]) -> int:
    if len(nums) == 0:
        return 0
    if len(nums) == 1:
        return nums[0]

    n = len(nums)
    dp = [0] * n
    dp[0] = nums[0]
    dp[1] = max(nums[1], dp[0]) 
    for i in range(2, n):
        dp[i] = max(dp[i-1],
                    nums[i] + dp[i-2])

    return dp[n-1]
    
# Recursion with memoization - O(n) time, O(n) space (memoization + recursion stack)
def rob(nums: list[int]) -> int:
    n = len(nums)

    def dfs(i: int, cache: dict[int, int]) -> int:
        if i >= n:
            return 0
        if i in cache:
            return cache[i]

        cache[i] = max(dfs(i+1, cache),
                       dfs(i+2, cache) + nums[i])
        return cache[i]

    return dfs(0, {})