leetcode-198 House Robber

# You are a professional robber planning to rob houses along a street.
# Each house has a certain amount of money stashed. All houses are arranged
# in a line, and adjacent houses have security systems connected.
# It will automatically contact the police if two adjacent houses are broken
# into on the same night.
# Given an integer array nums representing the amount of money of each house,
# return the maximum amount of money you can rob without alerting the police.
#
# Example 1:
# Input: nums = [1,2,3,1]
# Output: 4
# Explanation: Rob house 1 (money = 1) and house 3 (money = 3). Total = 4.
#
# Example 2:
# Input: nums = [2,7,9,3,1]
# Output: 12
# Explanation: Rob house 1, 3, and 5 (2 + 9 + 1 = 12).
#
# Constraints:
# 1 <= nums.length <= 100
# 0 <= nums[i] <= 400

class Solution:
    # Approach 1: DP with array
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        if len(nums) == 1:
            return nums[0]

        n = len(nums)
        dp = [0] * n
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])

        for i in range(2, n):
            # Either rob current house + max from i-2
            # Or don't rob current, take max from i-1
            dp[i] = max(nums[i] + dp[i-2], dp[i-1])

        return dp[n-1]

    # Approach 2: Space Optimized O(1)
    def rob2(self, nums: List[int]) -> int:
        if not nums:
            return 0

        # Only need previous two values
        prev2 = 0  # Max money 2 houses back
        prev1 = 0  # Max money 1 house back

        for num in nums:
            # Rob current + prev2, or skip current and take prev1
            current = max(num + prev2, prev1)
            prev2 = prev1
            prev1 = current

        return prev1

# Time Complexity: O(n)
# Space: O(n) for array DP, O(1) for optimized
#
# DP Recurrence: dp[i] = max(nums[i] + dp[i-2], dp[i-1])
# Pattern: At each step, choose to include current or not
# This pattern appears in many "house robber" variants!