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