# [LeetCode] 198. House Robber 打家劫舍

2021年09月15日 阅读数：2

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

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

Example 1:python

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

State: dp[i]，表示到第i个房子时可以抢到的最大金额。htm

Function: dp[i] = max(num[i] + dp[i - 2], dp[i - 1])blog

Initialize: dp[0] = num[0], dp[1] = max(num[0], num[1]) 或者 dp[0] = 0, dp[1] = 0get

Return: dp[n]it

Java:

```public class Solution {
public int rob(int[] nums) {
if(nums.length <= 1){
return nums.length == 0 ? 0 : nums[0];
}
// a是上次的最大收益
int a = nums[0];
// b是当前的最大受益
int b = Math.max(nums[0], nums[1]);
for(int i = 2; i < nums.length; i++){
int tmp = b;
// 当前的最大收益是两种选择里较大的那个
b = Math.max(a + nums[i], b);
a = tmp;
}
return b;
}
}
```

Java:

```class Solution {
public int rob(int[] nums) {
int curMax = 0, curPrePreMax = 0;
for (int cur : nums) {
int temp = curMax;
curMax = Math.max(curMax, curPrePreMax + cur);
curPrePreMax = temp;
}
return curMax;
}
}　```

Python:

```class Solution:
# @param num, a list of integer
# @return an integer
def rob(self, num):
if len(num) == 0:
return 0

if len(num) == 1:
return num[0]

num_i, num_i_1 = max(num[1], num[0]), num[0]
for i in xrange(2, len(num)):
num_i_1, num_i_2 = num_i, num_i_1
num_i = max(num[i] + num_i_2, num_i_1);

return num_i
```

Python:

```class Solution(object):
def containsDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
vis = set()
for num in nums:
if num in vis: return True
return False　　```

Python:

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

Python: wo

```class Solution(object):
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums:
return 0
if len(nums) == 1:
return nums[0]

pre_pre = nums[0]
pre = max(nums[0], nums[1])
for i in xrange(2, len(nums)):
cur = max(pre, pre_pre + nums[i])
pre_pre, pre = pre, cur

return pre 　　```

C++:

```class Solution {
public:
int rob(vector<int> &num) {
if (num.size() <= 1) return num.empty() ? 0 : num[0];
vector<int> dp = {num[0], max(num[0], num[1])};
for (int i = 2; i < num.size(); ++i) {
dp.push_back(max(num[i] + dp[i - 2], dp[i - 1]));
}
return dp.back();
}
};
```

C++:

```class Solution {
public:
int rob(vector<int> &nums) {
int a = 0, b = 0;
for (int i = 0; i < nums.size(); ++i) {
int m = a, n = b;
a = n + nums[i];
b = max(m, n);
}
return max(a, b);
}
};
```

[LeetCode] 213. House Robber II 打家劫舍 II