Python recursive solution. If one forget to add a cache (The dictionary `d`

in the following), the time complexity will be $O(2^n)$ and will give you TLE.

```
def rob(self, nums):
d = {}
def DP(nums):
if not nums: return 0
if len(nums) in d: return d[len(nums)]
d[len(nums)]=max(nums[0]+DP(nums[2:]),DP(nums[1:]))
return d[len(nums)]
return DP(nums)
```