# Q198 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.

##### 解题思路：

```当 n = 0 时，列表为空，返回 0

.....```

```设 k 为列表最大下标，则有：
f(0) = nums[0]
f(1) = max(num[0], num[1])
f(k) = max(f(k-2) + nums[k], f(k-1))```

##### Python实现：
```class Solution(object):
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
high = len(nums) - 1
if high == -1:
return 0
elif high == 0:
return nums[0]
elif high == 1:
return max(nums[0], nums[1])
else:
return max(self.rob(nums[:high-1]) + nums[high], self.rob(nums[:high]))```

```class Solution(object):
def rob2(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
# pre2 相当于 f(k-2), pre1 相当于 f(k-1), now 相当于 f(k)
pre2 = pre1 = now = 0
for num in nums:
pre2 = pre1
pre1 = now
now = max(pre2 + num, pre1)
return now

a = [6,3,10,8,2,10,3,5,10,5,3]
b = Solution()
print(b.rob2(a))  # 39  # 下标 [0, 2, 5, 8, 10] = 6 + 10 + 10 + 10 + 3 = 39```

```class Solution(object):
def rob3(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
last = now = 0
for num in nums:
last, now = now, max(last + num, now)
return now

a = [6,3,10,8,2,10,3,5,10,5,3]
b = Solution()
print(b.rob3(a))  # 39  # 下标 [0, 2, 5, 8, 10] = 6 + 10 + 10 + 10 + 3 = 39```

165 篇文章42 人订阅

0 条评论

## 相关文章

8720

### 包含min函数的栈

LeetCode 155. Min Stack 设计一个栈，支持如下操作，这些操作的算法复杂度需要是常数级，O(1) 1.push(x) : 将元素x压入...

10910

### 最大连续子序列和

https://blog.csdn.net/bitcarmanlee/article/details/51526010

11620

### 1341 与3和5无关的数

1341 与3和5无关的数 时间限制: 1 s 空间限制: 64000 KB 题目等级 : 白银 Silver 题目描述 Description ...

28940

### 第七天、判断三角形的类型

根据输入的三角形的三条边判断三角形的类型，并输出它的面积和类型。 C代码： /*第七天、判断三角形的类型*/ #include <stdio.h> ...

22400

9020

18500

56850

### NumPy简明教程（二、数组1）

http://blog.csdn.net/sunny2038/article/details/9002531

11010

21530