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

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

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

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)
• ProgramCreek: LeetCode House Robber