# 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
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]

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