5
$\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$
3
  • $\begingroup$ This problem is a restriction of the problem from this question where I provided a pretty sketchy proof sketch of NP-hardness. $\endgroup$ 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$ Nov 20 '16 at 17:29
0
$\begingroup$

I found a question which is similar to the 2D version of house robber

If you observe carefully we can calculate the answer for each row independently and that leads us to our solution.

Here is my solution for it

class Solution {
    public int solve(int[][] matrix) {
        int N = matrix.length;
        if(N == 0)
        return 0;
        int[] arr = new int[N];
        for(int i = 0; i < N; i++)
        arr[i] = DP(matrix[i]);
        int ans = DP(arr);
        return ans;        
    }

    public int DP(int[] arr) {
        int[] dp = new int[arr.length + 1];
        dp[0] = 0;
        dp[1] = arr[0];
        for(int i = 1; i < arr.length; i++) {
            dp[i + 1] = Math.max(dp[i],dp[i - 1] + arr[i]);
        }
        return dp[arr.length];
    }
}
$\endgroup$
1
  • 2
    $\begingroup$ Care to explain in plain English, what it does? Links tend to rot, could you write summary or quote relevant parts? $\endgroup$
    – Evil
    Jun 13 '21 at 1:45

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.