0198. House Robber

# 198. House Robber#

## 题目 #

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.
``````

## 解题思路 #

• 你是一个专业的小偷，打算洗劫一条街的所有房子。每个房子里面有不同价值的宝物，但是如果你选择偷窃连续的 2 栋房子，就会触发警报系统，编程求出你最多可以偷窃价值多少的宝物？
• 这一题可以用 DP 来解答，也可以用找规律的方法来解答。
• DP 的状态定义是：`dp[i]` 代表抢 `nums[0,i]` 这个区间内房子的最大值，状态转移方程是 `dp[i] = max(dp[i-1], nums[i]+dp[i-2])` 。可以优化迭代的过程，用两个临时变量来存储中间结果，以节约辅助空间。

## 代码 #

``````
package leetcode

// 解法一 DP
func rob198(nums []int) int {
n := len(nums)
if n == 0 {
return 0
}
if n == 1 {
return nums[0]
}
// dp[i] 代表抢 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]
}

// 解法二 DP 优化辅助空间，把迭代的值保存在 2 个变量中
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
}

// 解法三 模拟
func rob(nums []int) int {
// a 对于偶数位上的最大值的记录
// b 对于奇数位上的最大值的记录
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)
}

``````

Sep 6, 2020