### The Problem

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.

*Check LeetCode link for more details and example input & output.*

### A Dynamic Programming Solution

Use the bottom up approach.

`dp[i] = max(nums[i] + dp[i-2], dp[i-1])`

`dp[i]`

is the answer of the sub problem “i”,
whose input array is a sub-array of the orginal input `nums`

.
The sub-array starts at index `0`

and ends at index `i`

.

Base cases:

`dp[0]`

is`nums[0]`

.`dp[-1]`

is 0.*(It’s used to calculate*`dp[1]`

.)

#### Java Code

```
public int rob(int[] nums) {
int dp1 = nums[0]; // dp[i-1]
int dp2 = 0; // dp[i-2]
for (int i = 1; i < nums.length; i++) {
int tmp = dp1;
dp1 = Math.max(nums[i] + dp2, dp1);
dp2 = tmp;
}
return dp1;
}
```

The time complexity is `O(n)`

.