## 198. 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.

Credits:
Special thanks to @ifanchu for adding this problem and creating all test cases. Also thanks to @ts for adding additional test cases.

b'
\n
\n\n
\n

## Solution

\n
\n

#### Approach #1 (Dynamic Programming) [Accepted]

\n

Algorithm

\n

It could be overwhelming thinking of all possibilities on which houses to rob.

\n

A natural way to approach this problem is to work on the simplest case first.

\n

Let us denote that:

\n
\n

f(k) = Largest amount that you can rob from the first k houses.
\nAi = Amount of money at the ith house.

\n
\n

Let us look at the case `n = 1`, clearly f(1) = A1.

\n

Now, let us look at `n = 2`, which f(2) = max(A1, A2).

\n

For `n = 3`, you have basically the following two options:

\n
\n
1. \n

Rob the third house, and add its amount to the first house\'s amount.

\n
2. \n
3. \n

Do not rob the third house, and stick with the maximum amount of the first two houses.

\n
4. \n
\n

Clearly, you would want to choose the larger of the two options at each step.

\n

Therefore, we could summarize the formula as following:

\n
\n

f(k) = max(f(k \xe2\x80\x93 2) + Ak, f(k \xe2\x80\x93 1))

\n
\n

We choose the base case as f(\xe2\x80\x931) = f(0) = 0, which will greatly simplify our code as you can see.

\n

The answer will be calculated as f(n). We could use an array to store and calculate the result, but since at each step you only need the previous two maximum values, two variables are suffice.

\n
`public int rob(int[] num) {\n    int prevMax = 0;\n    int currMax = 0;\n    for (int x : num) {\n        int temp = currMax;\n        currMax = Math.max(prevMax + x, currMax);\n        prevMax = temp;\n    }\n    return currMax;\n}\n`
\n

Complexity analysis

\n
\n
• \n

Time complexity : .\nAssume that is the number of houses, the time complexity is .

\n
• \n
• \n

Space complexity : .

\n
• \n
\n
'