1
$\begingroup$

I came across a modification of the classic house robber problem where the robber cannot rob from $l(i)$ houses on the left of $i$th house and $r(i)$ houses on the right of $i$th house. The modified version will now be 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 if you rob the $i$th house then you cannot rob from $l(i)$ houses on the left of $i$th house and $r(i)$ houses on the right of $i$th house (in the classical problem, $l(i) = r(i) = 1$). Given the amount the money in each house, and the arrays $l$ and $r$, what is the optimal amount to be stolen?

I believe this can be solved by dynamic programming as well. However I have been trying enough without any results and would like some help on this.

Edit 1:
l(i) and r(i) are variable i.e. different for each i. Example:
House values: 1 3 7 3 7
L array: 0 0 2 2 2
R array: 3 0 1 0 0

The answer is 10, which is obtained by selecting the 2nd and 5th house. To further clarify l(i) and r(i), take the 3rd house for example. l is 2, means that 2 houses on the left cannot be selected (houses 1st and 2nd), whereas r is 1, meaning 1 house on the right cannot be selected (4th house)
Note: The convention for numbering used is, first house is i=1, second is i=2 and so on.

$\endgroup$
4
  • $\begingroup$ You can do something like: $DP[i] = max(DP[i - 1], DP[i - l(i) - 1] + money[i])$ $\endgroup$
    – klaus
    Nov 12, 2017 at 22:10
  • $\begingroup$ Mind giving an example? $\endgroup$ Nov 14, 2017 at 1:25
  • $\begingroup$ Are l(i) and r(i) arrays? Or a constant like l(i) = r(i) = k? $\endgroup$
    – klaus
    Nov 16, 2017 at 11:31
  • $\begingroup$ Added an edit to clarify the two doubts. $\endgroup$ Nov 17, 2017 at 22:18

0

Your Answer

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

Browse other questions tagged or ask your own question.