Problem

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 systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Examples

Example 1:

1
2
3
4

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

Example 2:

1
2
3
4

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

Similar Problems

House Robber 2 - Houses in circle House Robber 3 - Houses in Binary Tree House Robber 4

Solution

Method 1 - Dynamic Programming with Memorization

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

public int rob(int[] nums) {
	if (nums.length == 0) {
		return 0;
	}

	int[] mem = new int[nums.length + 1];
	Arrays.fill(mem, -1);

	mem[0] = 0;

	return helper(nums.length, mem, nums);
}

private int helper(int size, int[] mem, int[] nums) {
	if (size<1) {
		return 0;
	}

	if (mem[size] != -1) {
		return mem[size];
	}

	//two cases
	int firstSelected = helper(size - 2, mem, nums) + nums[nums.length - size];
	int firstUnselected = helper(size - 1, mem, nums);

	return mem[size] = Math.max(firstSelected, firstUnselected);
}

Method 2 - Dynamic Programming

The key is to find the relation dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i]).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

public int rob(int[] nums) {
	if (nums == null || nums.length == 0)
		return 0;

	if (nums.length == 1)
		return nums[0];

	int[] dp = new int[nums.length];
	dp[0] = nums[0];
	dp[1] = Math.max(nums[0], nums[1]);

	for (int i = 2; i<nums.length; i++) {
		dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
	}

	return dp[nums.length - 1];
}

Method 3 - DP without Extra Space 🏆

We can use two variables, rob1 and rob2, to track the maximum value so far as iterating the array. You can use the following example to walk through the code.

1

50 1 1 50

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

public int rob(int[] num) {
	if (num == null || num.length == 0)
		return 0;

	int rob1 = 0;
	int rob2 = 0;

	// rob1, rob2, houseN, houseN+1
	for (int num: nums) {
		int temp = Math.max(rob1+num, rob2);
		rob1 = rob2; // we are moving forward
		rob2 = temp;
	}

	return rob2;
}