198. House Robber

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

Difficulty: Medium

Topic: Dynamic Programming

This is a very typical dynamic programming problem. The key is to find the recursive formula.

Constraints:

• Cannot rob two adjacent houses.

Goal:

• Maximize the total amount of money you can rob tonight.

Base Case:

• when there is only one house, the robber can only rob this house.
• When there are two houses, the robber can only rob the house with more money.

Recursion:

• For the current house, the robber either robs it or not, it's a binary choice.
• To maximize the total amount of money, the robber will never give up both houses if they are consecutive. i.e. the robber either robs (the current house + the house after the next house), or the house after the current house.
• Bellman Equation: max(nums[i] + rob(nums[i + 2:]), rob(nums[i + 1:]))
• This recursion has lots of overlapping subproblems, so we can use dynamic programming to solve it.

In DP, we keep a memoization array. M[i] is the maximum amount of money the robber can rob from the first i houses (the robber may not actually robs the ith house, this is only the maximum he could get up to this house). The final result is M[n].

So we have the following recursive formula to fill in the memoization array in a bottom-up manner:

• M.append(max(nums[i] + M[i - 2], M[i - 1]))

Python

$O(n)$ time, $O(n)$ space.

44ms Beats 22.04% of users with Python3

Python is not a good language for comparing speed. It's slow and the time taken is always unstable/unpredictable.

This algorithm is already optimized. If I write it in C++ and Rust, it's much faster and beats 100% of people.

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        # Solution 1: Recursion
        # if n <= 2:
        #     return max(nums)
        # return max(nums[0] + self.rob(nums[2:]), self.rob(nums[1:]))

        # Solution 2: DP
        if n <= 2:
            return max(nums)
        M = [nums[0], max(nums[0], nums[1])]
        for i in range(2, n):
            M.append(max(nums[i] + M[i - 2], M[i - 1]))
        return M[-1]

Rust

$O(n)$ time, $O(n)$ space.

• Time: 0ms, Beats 100%

impl Solution {
    pub fn rob(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        if n <= 2 {
            return *nums.iter().max().unwrap() as i32;
        }
        let mut M = vec![nums[0], std::cmp::max(nums[0], nums[1])];
        for i in 2..n {
            M.push(std::cmp::max(nums[i] + M[i - 2], M[i - 1]));
        }
        return *M.last().unwrap() as i32;
    }
}

C++

$O(n)$ time, $O(n)$ space.

Beats 100% in time.

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n <= 2) {
            return *max_element(nums.begin(), nums.end());
        }
        vector<int> M;
        M.push_back(nums[0]);
        M.push_back(*max_element(nums.begin(), nums.begin() + 2));
        for (int i=2; i < n; i++) {
            M.push_back(max(nums[i] + M[i - 2], M[i - 1]));
        }
        return M.back();
    }
};