LC 198 - House Robber
Question
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 systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
Example 1:
1
2
Input: nums = [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:
1
2
Input: nums = [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.
Constraints:
1 <= nums.length <= 1000 <= nums[i] <= 400
Links
Question here and solution here
Solution
concept
solving from left to right
if we solve it in order, at every pos (e.g. n), we determine what is the max profit can be achieved from nums[0:n+1] (i.e. includes nth pos) at each pos there is 2 choices:
- rob the current house + the previous previous house (aggregated) profit since we cannot rob adj house
- do not rob current, and take the previous house profit we choose the max one out of the 2
solving from right to left
we need to make sure that dp[i] stores the maximum profit so far. This is because we can have array like [2,1,1,2] where the maximum profit is 4, in this case we take index 0 and 3 where we skipped 2 houses. If we simply do alternate robbing and store it in dp array we will get 3 which is wrong. This issue only occurs if we go from right to left (in memoization we have conditions that do 2 skips), so we have to store the maximum so far in the array.
code
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
class Solution:
"""
brute force
"""
def rob(self, nums: List[int]) -> int:
def dfs(i):
if i >= len(nums):
return 0
return max(nums[i] + dfs(i+2), dfs(i+1))
return dfs(0)
class Solution:
"""
dp: top down (memoization)
"""
def rob(self, nums: List[int]) -> int:
dp = [-1]*len(nums)
def dfs(i):
if i >= len(nums):
return 0
if dp[i] != -1:
return dp[i]
dp[i] = max(nums[i] + dfs(i+2), dfs(i+1))
return dp[i]
return dfs(0)
class Solution:
"""
bottom up
left -> right
"""
def rob(self, nums: List[int]) -> int:
n = len(nums)
dp = [0] * (n + 2)
# nums: [1,2,3,1]
# dp:[0,0,1,2,3,1], the first 2 0s are meant to make calculation abit easier
for i in range(2, len(dp)):
dp[i] = max(dp[i-2] + nums[i - 2], dp[i - 1])
return dp[-1]
class NeetSolution:
"""
bottom up
left -> right
"""
def rob(self, nums: List[int]) -> int:
if not nums:
return 0
if len(nums) == 1:
return nums[0]
dp = [0] * len(nums)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i - 1], nums[i] + dp[i - 2])
return dp[-1]
class Solution:
"""
bottom up
left -> right
space optimised
"""
def rob(self, nums: List[int]) -> int:
rob_1, rob_2 = 0, 0
# [. . . rob_1, rob_2, n, n + 1, ...]
for n in nums:
tmp = max(rob_2, rob_1 + n)
rob_1 = rob_2
rob_2 = tmp
return rob_2
class Solution:
"""
bottom up
right -> left
this is quite similar to left to right, you can think of it as robbing from reversed direction
"""
def rob(self, nums: List[int]) -> int:
if len(nums) <= 2:
return max(nums)
dp = [0] * len(nums)
dp[-1] = nums[-1]
dp[-2] = max(nums[-2], nums[-1])
for i in range(len(nums)-3, -1, -1):
dp[i] = max(nums[i] + dp[i+2], dp[i+1])
return dp[0]
Complexity
time: $O(n)$
space: $O(n)$