# 198. House Robber

## Approach 1: Keeping track of amount robbed using DP

```python
class Solution(object):
    def rob(self, nums):
        """
        https://leetcode.com/problems/house-robber/description/
        :type nums: List[int]
        :rtype: int
        """
        lea = len(nums)
        if lea == 0:
            return 0
        if lea == 1:
            return nums[0]
        if lea == 2:
            return max(nums)
        if lea == 3:
            return max(nums[0] + nums[2], nums[1])
        dp = [0] * lea
        dp[0], dp[1], dp[2] = nums[0], nums[1], nums[0] + nums[2]
        for i in range(3, lea):
            dp[i] = nums[i] + max(dp[i-2], dp[i-3])
        return max(dp[-1], dp[-2])
```

Here we keep track of the max sum from position 0 to `i` in `dp[i]`. This is calculated as follows `dp[i] = nums[i] + max(dp[i-2], dp[i-3])` 

Moreover the initial conditions are `dp[0]`, `dp[1]` and `dp[2]` which are initalised as `nums[0]`, `nums[1]` and `nums[0] + nums[2]` respectively.

In the end we only have to check the last two entries to see which one is greater and return the larger one.

> **Time Complexity:** *O(N)*
>
> **Space Complexity:** *O(N)*