198. House Robber #

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 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 1:

Input: [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:

Input: [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.

Problem Summary #

You are a professional thief planning to rob houses along a street. Each house has a certain amount of cash hidden inside. The only constraint affecting your robbery is that adjacent houses have interconnected security systems; if two adjacent houses are broken into on the same night, the system will automatically alert the police.

Given an array of non-negative integers representing the amount of money stored in each house, calculate the maximum amount you can steal without triggering the alarm system.

Solution Approach #

• You are a professional thief planning to rob all the houses on a street. Each house contains valuables of different values, but if you choose to rob 2 consecutive houses, the alarm system will be triggered. Write a program to find the maximum value of valuables you can steal.
• This problem can be solved with DP, or by finding the pattern.
• The DP state definition is: dp[i] represents the maximum value from robbing houses in the interval nums[0,i]; the state transition equation is dp[i] = max(dp[i-1], nums[i]+dp[i-2]). The iteration process can be optimized by using two temporary variables to store intermediate results, saving auxiliary space.

Code #

package leetcode

// Solution 1: DP
func rob198(nums []int) int {
	n := len(nums)
	if n == 0 {
		return 0
	}
	if n == 1 {
		return nums[0]
	}
	// dp[i] represents the maximum value from robbing houses nums[0...i]
	dp := make([]int, n)
	dp[0], dp[1] = nums[0], max(nums[1], nums[0])
	for i := 2; i < n; i++ {
		dp[i] = max(dp[i-1], nums[i]+dp[i-2])
	}
	return dp[n-1]
}

// Solution 2: DP, optimize auxiliary space by storing the iterative values in 2 variables
func rob198_1(nums []int) int {
	n := len(nums)
	if n == 0 {
		return 0
	}
	curMax, preMax := 0, 0
	for i := 0; i < n; i++ {
		tmp := curMax
		curMax = max(curMax, nums[i]+preMax)
		preMax = tmp
	}
	return curMax
}

// Solution 3: Simulation
func rob(nums []int) int {
	// a records the maximum value at even positions
	// b records the maximum value at odd positions
	a, b := 0, 0
	for i := 0; i < len(nums); i++ {
		if i%2 == 0 {
			a = max(a+nums[i], b)
		} else {
			b = max(a, b+nums[i])
		}
	}
	return max(a, b)
}