Problem statement
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
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
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.
Solutions
Approach 1: Dynamic Programming
This is it, this is the problem that covers everything you need to know about Dynamic Programming.
- Determine the choices required
In this case, the robber has two choices, he can either rob a house he’s at or skip it.
Now looking at the cases individually:
Case 1: Robbing the current house
If the current house is to be robbed, then neither the previous nor the next house can be robbed.
Case 2: Skipping the current house
If the current house is to be skipped, then either the previous house or the next house can be robbed.
In order to simplify, let us stick to just one direction(i.e., the robber only goes forwards).
- Determining which choice to pick
The choice which yields the highest money must be picked, which is essentially two cases:
Case 1: Robbing the current house: Loot of that house and the loot of next houses Case 2: Skipping the current house: Loot of the next house and the loot of next houses.
But before we determine which choice to pick, let us look at how one should approach a Dynamic Programming problem Taken from this LeetCode Discussion
Find the recurrence relation, basically a subproblem
if current_house is to be robbed, then current_house - 2 can be safely robbed
along with the loot from previous houses
if current house is to be skipped, then current_house - 1 can be safely robbed
along with the loot from the following houses
i.e., rob(i) = max(rob(i - 2) + current_house_value, rob(i-1))
Do note that in this approach, you start from the last house rather than the first.
Implementation in Python
def rob(self, nums: List[int]) -> int:
return back_tracker(nums, len(nums)-1)
def back_tracker(nums, i):
if i < 0:
return 0
return max(back_tracker(nums, i - 2) + nums[i], back_tracker(nums, i - 1))
Time Complexity: Unsure but $O(2^n)$ would be my guess
Runtime on LeetCode: Time Limit Exceeded
Optimizing the first approach
The drawback that previous approach has is that it re-computes certain values, we could save
a lot of time if we store the computed values somewhere and use them instead.
Simple memoization will get us very far in this case.
Implementation in Python
def rob(self, nums: List[int]) -> int:
memo = [-1] * (len(nums) +1 )
return back_tracker(nums, len(nums)-1, memo)
def back_tracker(nums, i, memo):
if i < 0:
return 0
if memo[i] >= 0:
return memo[i]
result = max(back_tracker(nums, i - 2, memo) + nums[i], back_tracker(nums, i - 1, memo))
memo[i] = result
return result
Time Complexity: $O(n)$?
Runtime on LeetCode: $36$ms
Iterative (bottom-up)
So far we’ve been starting at the last house and ending at first with maximum profits, but that is taking
a toll on our robbers because they need to find out which house is the last!
One way we could help our robbers is by giving them a starting location.
Basically just reversing the logic and converting the recursive function into an iterative one.
Implementation in Python
def rob(self, nums: List[int]) -> int:
memo = [0] * (len(nums) + 1)
memo[1] = nums[0] # current house
for i in range(1, len(nums)):
current_house = nums[i]
next_house = max(memo[i], current_house + memo[i-1])
memo[i+1] = next_house
return memo[len(nums)]
Slight improvement
We didn’t really need an entire list for memoization because we just used memo[i] and memo[i+1], so
that can be boiled down to just two variables
Implementation in Python
def rob(self, nums: List[int]) -> int:
prev_prev_house = 0
prev_house = 0
for num in nums:
current_house = max(prev_prev_house + num, prev_house)
prev_prev_house = prev_house
prev_house = current_house
return prev_house
Implementation in Rust
fn rob(nums: Vec<i32>) -> i32 {
let mut prev_prev_house = 0;
let mut prev_house = 0;
for num in nums.into_iter() {
let current_house = std::cmp::max(prev_prev_house + num, prev_house);
prev_prev_house = prev_house;
prev_house = current_house;
}
return prev_house
}
Far better and far easier to digest, whew, that was a long one!
Time Complexity: $O(n)$
Runtime on LeetCode: $2$ms
That was a long one. But I feel quite confident with Dynamic Programming now so that’s a very big plus.
House Robber II - Problem Statement
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system 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
Input: nums = [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.
Example 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.
Solution
This was pretty much the same problem as above but by skipping the first and last house because they’re next to each other. Which is why I did not create another post for this.
Implementation in Rust
fn rob(nums: Vec<i32>) -> i32 {
let skip_first = &nums[1..];
let skip_last = &nums[0..nums.len() - 1];
let rob_skip_first = helper(skip_first.to_vec());
let rob_skip_last = helper(skip_last.to_vec());
let max = std::cmp::max(rob_skip_first, rob_skip_last);
if nums[0] > max {
return nums[0];
}
max
}
fn helper(nums: Vec<i32>) -> i32 {
let mut prev_prev_house = 0;
let mut prev_house = 0;
for num in nums.into_iter() {
let current_house = std::cmp::max(prev_prev_house + num, prev_house);
prev_prev_house = prev_house;
prev_house = current_house;
}
return prev_house
}
Time Complexity: $O(n)$, it’s the same problem but runs two times.
Runtime on Leetcode: $1$ms