198. 打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 1：
1
2
3
4
| 输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
|
示例 2：
1
2
3
4
| 输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
|
DP
dp[i] 为抢到最后一家为 i 时，能抢到的最大金额，则转移方程为
$$
dp[i] = max(dp[i-2], dp[i-3]) + nums[i]
$$
因为 dp[i-4] 必小于 dp[i-2]，所以就不用考虑了；同理，也不用考虑 dp[i-5]
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
29
30
31
32
33
| func rob(nums []int) int {
// 排除特例
if len(nums) == 1 {
return nums[0]
}
if len(nums) == 2 {
return max(nums[0], nums[1])
}
if len(nums) == 3 {
return max(nums[1], nums[2]+nums[0])
}
dp := make([]int, len(nums))
dp[0] = nums[0]
dp[1] = nums[1]
dp[2] = nums[2] + dp[0]
res := max(dp[1], dp[2])
for i := 3; i < len(nums); i++ {
dp[i] = max(dp[i-2], dp[i-3]) + nums[i]
if dp[i] > res {
res = dp[i]
}
}
return res
}
func max(a, b int) int {
if a > b {
return a
} else {
return b
}
}
|
另一种思路 + 滚动数组
用 dp[i] 表示前 i 间房屋能偷窃到的最高总金额，那么就有如下的状态转移方程：
$$
dp[i]=max(dp[i−2]+nums[i],dp[i−1])
$$
最终的答案即为 dp[n−1]，其中 n 是数组的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| func rob(nums []int) int {
if len(nums) == 1 {
return nums[0]
}
if len(nums) == 2 {
return max(nums[0], nums[1])
}
dp := make([]int, len(nums))
dp[0] = nums[0]
dp[1] = max(nums[0],nums[1])
for i := 2; i < len(nums); i++ {
dp[i] = max(dp[i-1], dp[i-2]+nums[i])
}
return dp[len(nums)-1]
}
func max(a, b int) int {
if a > b {
return a
} else {
return b
}
}
|
然后用一下滚动数组捏
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| func rob(nums []int) int {
if len(nums) == 1 {
return nums[0]
}
if len(nums) == 2 {
return max(nums[0], nums[1])
}
var fir, sec, cur int
fir, sec = nums[0], max(nums[0], nums[1])
for i := 2; i < len(nums); i++ {
cur = max(sec, fir+nums[i])
fir = sec
sec = cur
}
return cur
}
func max(a, b int) int {
if a > b {
return a
} else {
return b
}
}
|
完美