# House Robber

## Question

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**

Given `[3, 8, 4]`, return `8`.

**Challenge**

O(n) time and O(1) memory.

**Tags**

LinkedIn Dynamic Programming Airbnb

**Related Problems**

Medium House Robber III 28 %\
Medium House Robber II 28 %\
Medium Paint House 35 %\
Easy Paint Fence 28 %\
Naive Fibonacci 25 %\
Easy Climbing Stairs

## Analysis

根据 **动态规划4要素** 进行分析：

类型：序列型动态规划

* 状态 State
  * f\[i] 表示前i个房子中,偷到的最大价值
* 方程 Function
  * f\[i] = max(f\[i-1], f\[i-2] + A\[i-1]);
* 初始化 Intialization
  * f\[0] = 0;
  * f\[1] = A\[0];
* 答案 Answer
  * f\[n]

状态转移方程将f\[i]分了两种情况（这里定义i是第i个房子，因此数组下标要减1，使用A\[i-1]）：\
1\. 去A\[i-1]，那么f\[i] = f\[i-2] + A\[i-1]\
2\. 不去A\[i-1]，那么f\[i] = f\[i-1]\
两者取最大值就是f\[i]

**滚动数组优化空间复杂度**

因为只与前面两个dp状态有关，因此可以通过滚动数组优化，状态转移方程变为：`dp[i%2] = Math.max(dp[(i-1)%2], dp[(i-2)%2] + A[i-1]);`\
优化后：Space O(1), Time O(n)

另：除了标准的4要素分析，利用O(n)空间的DP，以及通过滚动数组优化后O(1)空间的DP，还有一种更简便的利用O(1)空间的DP，基本思想是相同的，都是分解成为两种情况，rob当前的房子i，和不rob当前的房子i。不过因为只需要知道遍历完之后的最终结果，所以并不保留中间过程的变量，使得空间复杂度将为O(1)。当然空间复杂度都是O(n)，即遍历数组一遍。这种方法的本质其实正是滚动数组的优化。具体方法可以参考LeetCode讨论：<https://discuss.leetcode.com/topic/11082/java-o-n-solution-space-o-1/13>

## Solution

DP Solution（一维序列型动态规划） with O(n) space, O(n) time

```java
public class Solution {
    /**
     * @param A: An array of non-negative integers.
     * return: The maximum amount of money you can rob tonight
     */
    public int houseRobber(int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        }

        // Define DP state
        int[] dp = new int[A.length + 1];

        // Initialize DP
        dp[0] = 0;
        dp[1] = A[0];

        // DP Function
        for (int i = 2; i <= A.length; i++) {
            dp[i] = Math.max(dp[i-1], dp[i-2] + A[i-1]);
        }
        return dp[A.length];
    }
}
```

DP Solution Optimized with Rolling Array （滚动数组）, with O(1) space and O(n) time

```java
public class Solution {
    /**
    * @param A: An array of non-negative integers.
    * return: The maximum amount of money you can rob tonight
    */
    public int houseRobber(int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        }
        int []dp = new int[2];

        dp[0] = 0;
        dp[1] = A[0];

        for(int i = 2; i <= n; i++) {
            dp[i%2] = Math.max(dp[(i-1)%2], dp[(i-2)%2] + A[i-1]);
        }
        return dp[n%2];
    }
}
```

Two Variables with O(1) space, O(n) time

```java
public static int rob(int[] nums) {
    int ifRobbedPrevious = 0;     // max monney can get if rob current house
    int ifDidntRobPrevious = 0; // max money can get if not rob current house

    // We go through all the values, we maintain two counts, 1) if we rob this cell, 2) if we didn't rob this cell
    for(int i=0; i < nums.length; i++) {
        // If we rob current cell, previous cell shouldn't be robbed. So, add the current value to previous one.
        int currRobbed = ifDidntRobPrevious + nums[i];

        // If we don't rob current cell, then the count should be max of the previous cell robbed and not robbed
        int currNotRobbed = Math.max(ifDidntRobPrevious, ifRobbedPrevious);

        // Update values for the next round
        ifDidntRobPrevious  = currNotRobbed;
        ifRobbedPrevious = currRobbed;
    }

    return Math.max(ifRobbedPrevious, ifDidntRobPrevious);
}
```

## Reference

* [LeetCode: House Robber Java O(n) solution, space O(1)](https://discuss.leetcode.com/topic/11082/java-o-n-solution-space-o-1/13)
* [ProgramCreek: LeetCode House Robber](http://www.programcreek.com/2014/03/leetcode-house-robber-java/)