Blind 75.23 - House Robber II

House robber II.

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. 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.

Example 3:

Input: nums = [1,2,3]
Output: 3

Constraints:

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

Solution type

Caching via DP.

Solution

Fundamentally, we still have one of two choices at each house: rob or don’t rob. Our recurrence relation should therefore still be something along the lines of \(\textrm{rob}(i) = \textrm{max}(rob(\textrm{something}), \textrm{rob}(\textrm{something else}))\). The circular nature of the problem, however, makes the base case a little weird, since we don’t actually have a proper “starting point”.

I think what we might have to do is consider a circle of size 1, then a circle of size 2, then…essentially, instead of considering the circular nature at the very end, we should consider it throughout the entire problem? But this is also weird because the subproblems aren’t circles themselves; they’re arcs of the circle. I need to think about this one, the recurrence isn’t obvious to me.

Been thinking for 20 minutes, still stuck. The brute force way to do this is to enumerate all possible combinations of houses, scan them and rule out the ones that have adjacency, then calculate the earnings from each remaining valid combination and take the max. I want to use an \(O(n)\) size memo to store the max profit from considering the first \(i\) houses, but that doesn’t really help with the part where I have to rule out adjacency.

It should still definitely be two choices in the recurrence relation, not three or anything weird like that. It’s just weird because it feels like I need to keep two memos: one where I can’t rob the first house, and one where I can.

…

Oh god I feel so stupid.

def rob(self, nums: List[int]) -> int:
    memoWithFirst, memoWithoutFirst = [0 for _ in range(len(nums))], [0 for _ in range(len(nums))]
    memoWithFirst[0] = nums[0]
    if len(nums) >= 2:
        memoWithFirst[1] = nums[0]
        memoWithoutFirst[1] = nums[1]
    # if len(nums) >= 3:
    #     memoWithFirst[2] = max(nums[0], nums[1])
    #     memoWithoutFirst[2] = max(nums[1], nums[2])
    for i in range(2, len(nums)):
        memoWithFirst[i] = max(nums[i - 1] + memoWithFirst[i - 3], memoWithFirst[i - 1])
        memoWithoutFirst[i] = max(nums[i] + memoWithoutFirst[i - 2], memoWithoutFirst[i - 1])
    return max(memoWithFirst[-1], memoWithoutFirst[-1])

This is what I had at the end of time. I cheated and went for a few minutes longer, and I got the solution – because I figured out a correct way to solve the problem at the last minute. This is an ugly solution and I missed a tricky edge case on 1-size lists (because the default code actually can’t handle it correctly), but it does pass.

def rob(self, nums: List[int]) -> int:
    if len(nums) == 1:
        return nums[0]

    robbedWithFirst, notRobbedWithFirst = 0, 0
    for i in range(len(nums) - 1):
        robCurrent = nums[i] + notRobbedWithFirst 
        dontRobCurrent = max(robbedWithFirst, notRobbedWithFirst)
        robbedWithFirst = robCurrent
        notRobbedWithFirst = dontRobCurrent
    bestWithFirst = max(robbedWithFirst, notRobbedWithFirst)
    robbedWithoutFirst, notRobbedWithoutFirst = 0, 0
    for i in range(1, len(nums)):
        robCurrent = nums[i] + notRobbedWithoutFirst 
        dontRobCurrent = max(robbedWithoutFirst, notRobbedWithoutFirst)
        robbedWithoutFirst = robCurrent
        notRobbedWithoutFirst = dontRobCurrent
    bestWithoutFirst = max(robbedWithoutFirst, notRobbedWithoutFirst)
    return max(bestWithFirst, bestWithoutFirst)

Okay, to explain - if you rob the last house, then you can just run the house robber solver on indices 1 to len(nums) - 1. If you rob the first house, then you can just run the solver on indices 0 to len(nums) - 2. This is enough to get the solution - simple as that.

It feels like you should be able to just solve the middle portion (indices 1 to len(nums) - 2) and then do one individual calculation for both cases. However, direction matters: the house robber problem is solved going from one end of the row to another, and because you are accumulating the max profit, you can’t just calculate it one direction and then do another calculation from the wrong end. All this is to say: you can’t correctly calculate what the profit would be with the first house included without starting at the first house (or going in reverse order, but then this introduces the same problem when considering the profit with the last house included). In any case, you’re not getting better than this in time or memory complexity-wise.

Something I was thinking about while solving this problem is how to make it harder - for example, what if instead of the directly adjacent houses, the alarm went off if you robbed houses that were two indices away, or 3, or \(k\) indices? I am sure there’s a programmatic solution for that, but I wonder if it’s still a polynomial time algorithm. My guess is that it would be, but that the computation might have \(k\) as a factor in the O-complexity or something. In the context of this circular house robber problem, you’d also probably need to solve the basic house robber problem \(k + 1\) different times to account for the \(k + 1\) adjacent houses that would overlap across the end of the nums list.

Well, I feel a lil’ stupid. To be fair, the realization is less about coming up with some brilliant new recurrence relation (which there isn’t, really) and more about cleverly recasting the problem as a previous one. In any case, onto the next!