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

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

1. 去A[i-1]，那么f[i] = f[i-2] + A[i-1]
2. 不去A[i-1]，那么f[i] = f[i-1]
两者取最大值就是f[i]

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;
dp = A;

// 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;

dp = 0;
dp = A;

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);
}