Blind 75.22 - House Robber

House robber.

Problem description

Taken directly from LeetCode.

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.

Constraints:

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 400

Solution type

Caching via DP.

Solution

Our recurrence relationship just looks at the previous two steps in the past: for the \(i\)th, the best profit \(\textrm{rob}(i)\) is \(\textrm{max}(\textrm{rob}(i - 1), \textrm{rob}(i - 2) + \texttt{nums[i]})\). Either you don’t rob the \(i\)th house, in which case just take the best profit you could’ve gotten from considering the first \(i - 1\) houses, or you rob it and add on the best profit you could’ve gotten from the first \(i - 2\) houses (since you could not have robbed the \(i - 1\)th house).

int rob(vector<int>& nums) {
    if (nums.size() == 1) {
        return nums.back();
    }
    vector<int> memo(nums.size(), 0);
    memo[0] = nums[0];
    memo[1] = max(nums[0], nums[1]);
    for (int i = 2; i < nums.size(); ++i) {
        memo[i] = max(memo[i - 1], memo[i - 2] + nums[i]);
    }
    return memo.back();
}

I forgot the 1-size edge case and missed a test case because of that. I do feel like there should be a way to do this problem that starts iteration at i = 1 instead of i = 2, which would look cleaner…

While this is time-efficient, it uses more memory than necessary. You can actually just use two accumulator variables to track the maximal profit, since you only ever need to look back two steps in the past. There’s a perfectly fine, clean solution by lancertech6 on LeetCode that I’ll share here; you can view the original writeup at https://leetcode.com/problems/house-robber/solutions/4600148/beats-100-c-java-python-js-explained-with-video-dynamic-programming-space-optimized/.

int rob(vector<int>& nums) {
    int rob = 0;
    int norob = 0;
    for (int i = 0; i < nums.size(); i++) {
        int newRob = norob + nums[i];
        int newNoRob = max(norob, rob);
        rob = newRob;
        norob = newNoRob;
    }
    return max(rob, norob);
}

In an actual interview, I’m thinking way more about time efficiency than memory efficiency, so someone would likely have to prompt me on the memory efficiency for me to start thinking about it.

Aside: the title makes me want to think of the knapsack problem, but it’s not really the same thing. 0-1 knapsack can be solved in pseudo-polynomial time using DP - that is, it’s polynomial depending on the floating point precision of your values.