## Description

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 system connected and **it will automatically contact the police if two adjacent houses were broken into on the same night**.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight **without alerting the police**.

**Example 1:**

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

**Example 2:**

Input:[2,7,9,3,1]Output:12Explanation: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.

## Explanation

Dynamic programming approach. f(k) = max(f(k – 2) + Ak, f(k – 1))

## Python Solution

```
class Solution:
def rob(self, nums: List[int]) -> int:
if nums == None or len(nums) == 0:
return 0
if len(nums) == 1:
return nums[0]
n = len(nums)
f = [0 for i in range(0, n)]
f[0] = nums[0]
f[1] = max(f[0], nums[1])
for i in range(2, n):
f[i] = max(f[i - 1], f[i - 2] + nums[i])
return f[n - 1]
```

- Time complexity: O(n).
- Space complexity: O(n).

## One Thought to “LeetCode 198. House Robber”