2
$\begingroup$

This is a similar question to A variant of the house robber problem but instead of the general case, I'm wondering how you would solve the standard house robber problem, but when you cannot rob from houses on both the left and the right at the same time. The problem is modified from leetcode as follows:

"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 three 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. So for the array [2, 5, 10, 7, 11] the max you may rob is 26 by robbing houses with values 5, 10, and 11."

I came across this by misreading the original question (lol) but after working on the modified version I think there is a DP solution here but it seems somewhat complicated and might involve turning the array into DAGs.

$\endgroup$
1

1 Answer 1

1
$\begingroup$

Consider the first three houses (assuming $n \geq 3$). Any solution does not rob one of them, say the first one (you can enumerate over all three options). The remaining houses form a street, which enables us to solve the problem using a simple dynamic programming: for each $0 \leq i \leq 2$ and $j$, we find out the best solution for the first $j$ houses assuming that houses $j-1,\ldots,j-i$ are robbed.

$\endgroup$
2
  • $\begingroup$ Can you explain at a bit greater depth? I'm still having a hard time understanding the solution from what you wrote. $\endgroup$ Sep 24, 2021 at 15:46
  • $\begingroup$ I'm sorry, you'll have to work it out. $\endgroup$ Sep 24, 2021 at 15:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.