# 2D version of LeetCode house robber problem

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 ?

• This problem is a restriction of the problem from this question where I provided a pretty sketchy proof sketch of NP-hardness. – Tom van der Zanden Jun 16 '15 at 10:23
• @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 ? – Nihl Jun 16 '15 at 14:03
• @TomvanderZanden what if the houses are arranged in a circular fashion how does the solution change? – Shubham Singh rawat Nov 20 '16 at 17:29