198. House Robber

  • 37.9%

https://leetcode.com/problems/house-robber/#/description

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.


美团点评 面试

方法一:

  1. rob(i)表示偷了第i家,notrob(i) 不偷第i家。
  2. rob(i) = rob(i-1)+nums[i] ,notrob(i) = max(rob(i-1), notrob(i-1))

我的代码实现:

更新公式

rob(i) = max(rob(i-1), notrob(i-1)+nums[i]);

notrob(i) = max(rob(i-1), notrob(i-1));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
if(n==0)
return 0;
if(n==1)
return nums[0];
int rob = nums[0], notrob = 0;
for(int i=1; i<n; i++){
int new_rob = max(rob, notrob+nums[i]);
int new_notrob = max(rob, notrob);
rob = new_rob;
notrob = new_notrob;
}
return max(rob, notrob);
}
};

方法二:

由方法一进行推论可以得到

  1. f(i+1) 表示偷到第i家的最大利益, f(0) = 0, f(1) = nums[1]
  2. 则f(i+1) = max(f(i), f(i-1)+nums[i])

https://discuss.leetcode.com/topic/32215/c-dp-solution-with-thinking-process-explanation

C++ DP solution with thinking process explanation

Following the same logic described in a post about Best Time to Buy and Sell Stock with Cooldown, we could try to solve this problem with DP.

Define the following variables

rob[i] means max profit for any robbing sequence before house i ending with rob

rest[i] mean max profit for any robbing sequence before house i ending with rest

We could get the following relationship,

1
2
rob[i]  = max(rob[i-1], rest[i-1] + value)
rest[i] = max(rest[i-1], rob[i-1])

Furthermore, we always gain more profit when robbing the house. As a result,

1
2
rob[i] > rest[i]
rest[i] = rob[i-1]

substitute these into the original equations, we get

1
rob[i]  = max(rob[i-1], rob[i-2] + value)

So we only need two values to keep track of the max profit.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
int rob(vector<int>& nums) {
auto best = 0, prev_best = 0;
for(auto num : nums)
{
auto pbest = best;
best = max(best, prev_best + num);
prev_best = pbest;
}
return best;
}
};

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
if(n==0) return 0;
int r1 = 0, r2 = 0;
int r3 = 0;
for(auto num:nums){
r3 = max(r2, r1+num);
r1 = r2;
r2 = r3;
}
return r3;
}
};

https://discuss.leetcode.com/topic/28369/the-correct-dp-solution

The correct DP solution

Here is the DP formula that leads to the right answer:

M(k) = money at the kth house

P(0) = 0

P(1) = M(1)

P(k) = max(P(k−2) + M(k), P(k−1))


https://discuss.leetcode.com/topic/11110/c-1ms-o-1-space-very-simple-solution

C 1ms, O(1)space, very simple solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#define max(a, b) ((a)>(b)?(a):(b))
int rob(int num[], int n) {
int a = 0;
int b = 0;

for (int i=0; i<n; i++)
{
if (i%2==0)
{
a = max(a+num[i], b);
}
else
{
b = max(a, b+num[i]);
}
}

return max(a, b);
}

https://discuss.leetcode.com/topic/17199/python-solution-3-lines

Python solution, 3 lines.

Based on the recursive formula:

f(0) = nums[0]

f(1) = max(num[0], num[1])

f(k) = max( f(k-2) + nums[k], f(k-1) )

1
2
3
4
5
6
7
8
9
class Solution:

def rob(self, nums):

last, now = 0, 0

for i in nums: last, now = now, max(last + i, now)

return now

https://discuss.leetcode.com/topic/12735/c-my-solution-dp

C++,My solution,DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
int rob(vector<int>& nums) {
const int n = nums.size();
if (n == 0) return 0;
if (n == 1) return nums[0];
if (n == 2) return max(nums[0], nums[1]);
vector<int> f(n, 0);
f[0] = nums[0];
f[1] = max(nums[0], nums[1]);
for (int i = 2; i < n; ++i)
f[i] = max(f[i-2] + nums[i], f[i-1]);
return f[n-1];
}
};

44ms, 31.77%, 69/69, April.25, 2016

https://leetcode.com/discuss/76958/3-line-python-solution

Python solution, 3 lines.

Based on the recursive formula:

1
2
3
f(0) = nums[0]
f(1) = max(num[0], num[1])
f(k) = max( f(k-2) + nums[k], f(k-1) )
1
2
3
4
5
6
7
8
9
class Solution:

def rob(self, nums):

last, now = 0, 0

for i in nums: last, now = now, max(last + i, now)

return now

my code

rob[i] = notrob[i-1] + nums[i]

notrob[i] = max(rob[i-1], notrob[i-1])

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
def rob(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums: return 0
rob, notrob = 0, 0
for num in nums:
temp = rob
rob = notrob + num
notrob = max(temp, notrob)
return max(rob, notrob)
谢谢你,可爱的朋友。