4
$\begingroup$

The house robber problem of leetcode can be described as followed :

A robber enters a colony of houses numbered from 1 to n. Every house has a number printed on the top of it. That number is the amount of money inside that house. However, there is one constraint. If the robber robs the i-th house, he can't rob house no i-1 and house no i+1. How can the robber maximise his robbery?

Apparently, this is a classical problem in dynamic programming, which can be solved in linear complexity: See here and here.

My question : what about the 2D version ? if the houses are not on a line, but on a 2D grid ? Like for the 1D version, if you rob one house, you cannot rob the adjacent ones (see the following pattern) :

x x x
x o x
x x x

Can DP be used to solve that ? Is it even linearly solvable ?

$\endgroup$
  • $\begingroup$ This problem is a restriction of the problem from this question where I provided a pretty sketchy proof sketch of NP-hardness. $\endgroup$ – Tom van der Zanden Jun 16 '15 at 10:23
  • $\begingroup$ @TomvanderZanden : thank you for the link. So here you advise to represent the grid as a graph and the problem as a minimum vertex cover ? When you say it's NP-hard, do you mean in the strong sense ? $\endgroup$ – Nihl Jun 16 '15 at 14:03
  • $\begingroup$ @TomvanderZanden what if the houses are arranged in a circular fashion how does the solution change? $\endgroup$ – Shubham Singh rawat Nov 20 '16 at 17:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.