# LeetCode Solution, Medium, 198. House Robber

# [198. House Robber](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`

### 題目翻譯

假設你是一個專業的搶匪，今天的目標是要搶劫一條街上的房子。每個房子都有防盜系統，其條件是當同一晚相鄰的兩間房子都被闖入時會報警。給定一個陣列 `nums`，每個索引代表每間房子最多可以搶到多少錢。計算出最多可以搶到多少錢。

## 解法解析

其解法可以分為三種：Recursion、Iteration 和空間優化後的 Iteration。因為搶了第一間房子的話就不能搶第二間，解答是依據每次的選擇堆疊而成的。所以是典型的 Dynamic programming 問題。

主要的關鍵邏輯就是，每次選擇房子的時候是拿後面兩個來比較。目前在 i = 0 的位置，因為搶了 i = 0 的房子的話，就不能搶 i = 1 的房子。這樣的話至少 `i[0] + i[2]` >= i[1]` 才比較有效益，不然的話就是選擇 `i[1]` 的房子了。每次的選擇都是基於此條件，最後堆疊出最後的答案。

### 解法範例

#### Go

##### Recursion with Memoization

```go
func rob(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	var memo map[int]int = make(map[int]int, len(nums))
	return robFrom(memo, 0, nums)
}

func robFrom(memo map[int]int, i int, nums []int) int {
	if i >= len(nums) {
		return 0
	}

	if _, ok := memo[i]; ok {
		return memo[i]
	}
	if robFrom(memo, i+1, nums) > robFrom(memo, i+2, nums)+nums[i] {
		memo[i] = robFrom(memo, i+1, nums)
	} else {
		memo[i] = robFrom(memo, i+2, nums) + nums[i]
	}
	return memo[i]
}
```

##### Dynamic Programming

```go
func rob(nums []int) int {
	if len(nums) == 0 {
		return 0
	}

	var N int = len(nums)
	var maxRobbedAmount []int = make([]int, N+1)

	maxRobbedAmount[N], maxRobbedAmount[N-1] = 0, nums[N-1]
	for i := N - 2; i >= 0; i-- {
		if maxRobbedAmount[i+1] > maxRobbedAmount[i+2]+nums[i] {
			maxRobbedAmount[i] = maxRobbedAmount[i+1]
		} else {
			maxRobbedAmount[i] = maxRobbedAmount[i+2] + nums[i]
		}
	}
	return maxRobbedAmount[0]
}
```

##### Optimized Dynamic Programming

```go
func rob(nums []int) int {
	if len(nums) == 0 {
		return 0
	}
	var N int = len(nums)
	var robNext, robNextPlusOne int = nums[N-1], 0
	for i := N - 2; i >= 0; i-- {
		if robNext > robNextPlusOne+nums[i] {
			robNext, robNextPlusOne = robNext, robNext
		} else {
			robNext, robNextPlusOne = robNextPlusOne+nums[i], robNext
		}
	}
	return robNext
}
```

#### JavaScript

##### Recursion with Memoization

```javascript
/**
 * @param {number[]} nums
 * @return {number}
 */
const rob = function (nums) {
    const memo = {};

    const robFrom = (i, rob_nums) => {
        if (i >= rob_nums.length) {
            return 0;
        }
        if (i in memo) {
            return memo[i];
        }
        const ans = Math.max(rob_nums[i] + robFrom(i + 2, rob_nums), robFrom(i + 1, rob_nums));
        memo[i] = ans;
        return ans;
    };

    return robFrom(0, nums);
};
```

##### Dynamic Programming

```javascript
/**
 * @param {number[]} nums
 * @return {number}
 */
const rob = function (nums) {
    if (!nums) {
        return 0;
    }

    const N = nums.length;
    const maxRobbedAmount = new Array(N + 1).fill(0);
    maxRobbedAmount[N] = 0;
    maxRobbedAmount[N - 1] = nums[N - 1];

    for (let i = N - 2; i >= 0; i--) {
        maxRobbedAmount[i] = Math.max(nums[i] + maxRobbedAmount[i + 2], maxRobbedAmount[i + 1]);
    }
    return maxRobbedAmount[0];
};
```

##### Optimized Dynamic Programming

```javascript
/**
 * @param {number[]} nums
 * @return {number}
 */
const rob = function (nums) {
    if (!nums) {
        return 0;
    }

    const N = nums.length;
    let robNextPlusOne = 0,
        robNext = nums[N - 1];

    for (let i = N - 2; i >= 0; i--) {
        const current = Math.max(robNext, robNextPlusOne + nums[i]);
        robNextPlusOne = robNext;
        robNext = current;
    }
    return robNext;
};
```

#### Kotlin

##### Recursion with Memoization

```kotlin
class Solution {
    protected lateinit var memo: MutableMap<Int, Int>

    fun rob(nums: IntArray): Int {
        memo = mutableMapOf()
        return robFrom(0, nums)
    }

    fun robFrom(i: Int, nums: IntArray): Int {
        if (i >= nums.size) return 0
        if (memo[i] != null) return memo[i]!!
        val res = Math.max(robFrom(i + 1, nums), nums[i] + robFrom(i + 2, nums))
        memo[i] = res
        return res
    }
}
```

##### Dynamic Programming

```kotlin
class Solution {
    fun rob(nums: IntArray): Int {
        if (nums.size == 0) {
            return 0
        }

        val N: Int = nums.size
        var maxRobbedAmount: IntArray = IntArray(N + 1)
        maxRobbedAmount[N] = 0
        maxRobbedAmount[N - 1] = nums[N - 1]
        for (i in N - 2 downTo 0) {
            maxRobbedAmount[i] = Math.max(maxRobbedAmount[i + 1], maxRobbedAmount[i + 2] + nums[i])
        }
        return maxRobbedAmount[0]
    }
}
```

##### Optimized Dynamic Programming

```kotlin
class Solution {
    fun rob(nums: IntArray): Int {
        if (nums.size == 0) {
            return 0
        }

        val N: Int = nums.size
        var robNext: Int = nums[N - 1]
        var robNextPlusOne: Int = 0
        for (i in N - 2 downTo 0) {
            val current: Int = Math.max(robNext, robNextPlusOne + nums[i])
            robNextPlusOne = robNext
            robNext = current
        }
        return robNext
    }
}
```

#### PHP

##### Recursion with Memoization

```php
class Solution
{
    private $memo = [];

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function rob($nums)
    {
        return $this->robFrom(0, $nums);
    }

    function robFrom($i, $nums)
    {
        if ($i >= count($nums)) {
            return 0;
        }
        if (isset($this->memo[$i])) {
            return $this->memo[$i];
        }
        $ans = max($this->robFrom($i + 1, $nums), $this->robFrom($i + 2, $nums) + $nums[$i]);
        $this->memo[$i] = $ans;
        return $ans;
    }
}
```

##### Dynamic Programming

```php
class Solution
{
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function rob($nums)
    {
        if (empty($nums)) {
            return 0;
        }
        $N = count($nums);
        $maxRobbedAmount = array_fill(0, $N + 1, 0);
        $maxRobbedAmount[$N] = 0;
        $maxRobbedAmount[$N - 1] = $nums[$N - 1];
        for ($i = $N - 2; $i >= 0; $i--) {
            $maxRobbedAmount[$i] = max($maxRobbedAmount[$i + 1], $maxRobbedAmount[$i + 2] + $nums[$i]);
        }
        return $maxRobbedAmount[0];
    }
}
```

##### Optimized Dynamic Programming

```php
class Solution
{
    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function rob($nums)
    {
        if (empty($nums)) {
            return 0;
        }
        $N = count($nums);
        $robNext = $nums[$N - 1];
        $robNextPlusOne = 0;
        for ($i = $N - 2; $i >= 0; $i--) {
            $current = max($robNext, $robNextPlusOne + $nums[$i]);
            $robNextPlusOne = $robNext;
            $robNext = $current;
        }
        return $robNext;
    }
}
```

#### Python

##### Recursion with Memoization

```python
class Solution:
    def __init__(self) -> None:
        self.memo: dict[int, int] = {}

    def rob(self, nums: list[int]) -> int:
        self.memo = {}
        return self.robFrom(0, nums)

    def robFrom(self, i: int, nums: list[int]) -> int:
        # No more houses left to examine.
        if i >= len(nums):
            return 0

        # Return cached value.
        if i in self.memo:
            return self.memo[i]

        # Recursive relation evaluation to get the optimal answer.
        ans: int = max(self.robFrom(i + 1, nums), self.robFrom(i + 2, nums) + nums[i])

        # Cache for future use.
        self.memo[i] = ans
        return ans
```

##### Dynamic Programming

```python
class Solution:
    def rob(self, nums: list[int]) -> int:
        # Special handling for empty case.
        if not nums:
            return 0

        N: int = len(nums)
        maxRobbedAmount: list[int | None] = [None for _ in range(N + 1)]

        # Base case initialization.
        maxRobbedAmount[N], maxRobbedAmount[N - 1] = 0, nums[N - 1]

        # DP table calculations.
        for i in range(N - 2, -1, -1):

            # Same as recursive solution.
            maxRobbedAmount[i] = max(
                maxRobbedAmount[i + 1], maxRobbedAmount[i + 2] + nums[i]
            )

        return maxRobbedAmount[0]
```

##### Optimized Dynamic Programming

```python
class Solution:
    def rob(self, nums: list[int]) -> int:

        # Special handling for empty case.
        if not nums:
            return 0

        N: int = len(nums)

        rob_next_plus_one: int = 0
        rob_next: int = nums[N - 1]

        # DP table calculations.
        for i in range(N - 2, -1, -1):

            # Same as recursive solution.
            current: int = max(rob_next, rob_next_plus_one + nums[i])

            # Update the variables
            rob_next_plus_one = rob_next
            rob_next = current

        return rob_next
```

#### Rust

```rust
```

#### Swift

##### Recursion with Memoization

```swift
class Solution {

    var memo: [Int: Int] = [Int: Int]()

    func rob(_ nums: [Int]) -> Int {
        return robFrom(0, nums: nums)
    }

    func robFrom(_ i: Int, nums: [Int]) -> Int {
        if i >= nums.count {
            return 0
        }
        if let memoized: Int = memo[i] {
            return memoized
        }
        let result: Int = max(robFrom(i + 1, nums: nums), nums[i] + robFrom(i + 2, nums: nums))
        memo[i] = result
        return result
    }
}
```

##### Dynamic Programming

```swift
class Solution {
    func rob(_ nums: [Int]) -> Int {
        if nums.count == 0 {
            return 0
        }

        let N: Int = nums.count
        var maxRobbedAmount: [Int] = Array(repeating: 0, count: N + 1)
        maxRobbedAmount[N] = 0
        maxRobbedAmount[N - 1] = nums[N - 1]

        for i: Int in (0..<N - 1).reversed() {
            maxRobbedAmount[i] = max(maxRobbedAmount[i + 1], nums[i] + maxRobbedAmount[i + 2])
        }

        return maxRobbedAmount[0]
    }
}
```

##### Optimized Dynamic Programming

```swift
class Solution {
    func rob(_ nums: [Int]) -> Int {
        if nums.count == 0 {
            return 0
        }

        let N: Int = nums.count
        var robNextPlusOne: Int = 0
        var robNext: Int = nums[N - 1]

        for i: Int in (0..<N - 1).reversed() {
            let current: Int = max(robNext, nums[i] + robNextPlusOne)
            robNextPlusOne = robNext
            robNext = current
        }
        return robNext
    }
}
```