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 xx o xx x xCan DP be used to solve that ? Is it even linearly solvable ?
2D version of LeetCode house robber problem
algorithms;dynamic programming