[link](https://leetcode.com/problems/house-robber/)

---

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were 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 tonight without alerting the police.

#### Example 1:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

#### Example 2:

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

#### Constraints:

- 1 <= nums.length <= 100
- 0 <= nums[i] <= 400

---

The initial check if not nums: ensures that the input list is not empty. If it is empty, the function returns None. The code uses a dynamic programming approach to calculate the maximum amount that can be robbed at each house.

The for loop iterates from the third element (index 2) to the last element of nums. For each house at index i, a variable cur is initialized to i - 2 to start considering the houses two steps back.

A temporary list tmp is created to store the maximum amount that can be robbed when considering the current house and the houses two steps back. A nested while loop iterates while cur is greater than or equal to 0, considering the houses two steps back.

In each iteration of the nested loop, the amount of money that can be robbed at the current house and the house two steps back is calculated by adding nums[i] and nums[cur], and the result is appended to the tmp list. After the nested loop completes, the maximum amount that can be robbed at the current house is updated to be the maximum value in the tmp list.

The original list nums is modified, replacing the value at index i with the updated maximum amount. Once the for loop completes, the maximum amount that can be robbed is determined by taking the maximum value in the nums list. The maximum amount is returned as the result.

#### Solution 1: Brute force

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return None

        for i in range(2, len(nums)):
            cur = i - 2
            tmp = []
            while cur >= 0:
                tmp.append(nums[i] + nums[cur])
                cur -= 1
            
            nums[i] = max(tmp)
        
        return max(nums)
        

O(T): O(n^2)
O(S): O(n)

---

The rob function takes a list of integers nums representing the amount of money in each house and returns the maximum amount that can be robbed. The code uses a dynamic programming approach with constant space to calculate the maximum amount that can be robbed.

Two variables, rob1 and rob2, are initialized to 0. These variables represent the maximum amount of money that can be robbed for the previous two houses and the current house, respectively.

The code iterates through each house in the nums list. For each house, the code calculates the maximum amount of money that can be robbed by comparing two options:

- Robbing the current house and adding its value to the maximum amount that can be robbed from the previous two houses (n + rob1).
- Not robbing the current house and keeping the maximum amount that can be robbed from the previous house (rob2).

The code updates the rob1 and rob2 variables accordingly. rob1 is set to the previous rob2 value, and rob2 is set to the calculated maximum amount. Once the iteration through all the houses is complete, the maximum amount that can be robbed is stored in the rob2 variable. The maximum amount is returned as the result.

#### Solution 2: Bottom Up Dynamic Programming

class Solution:
    def rob(self, nums: List[int]) -> int:
        # dp
        # [rob1, rob2, n, n + 1, ...]
        rob1, rob2 = 0, 0
        for n in nums:
            tmp = max(n + rob1, rob2)
            rob1 = rob2
            rob2 = tmp
        
        return rob2
        

O(T): O(n)
O(S): O(1)