algorithm - 二维房屋强盗算法

这似乎是LeetCode House Robber问题的一个变体，但我发现很难解决：
在nxn网格上有一些房子。众所周知，每所房子都有一些贵重物品。劫匪的任务是抢劫尽可能多的房屋，以最大程度地掠夺赃物。然而，这里有一个安全系统，如果你抢劫了两个相邻的房子（左边，右边，上面和下面），警报就会响。找出抢劫者抢劫的最大战利品。

      Houses   :  alignment
     10 20 10      0  1  0
     20 40 20  =>  1  0  1
     10 20 10      0  1  0

   This alignment results in the maximum of 80.

我从https://shanzi.gitbooks.io/algorithm-notes/problem_solutions/house_robber.html学会了如何通过动态规划解决单列房屋的最佳选择：

public class HouseRobber {
    public int rob(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];

        int[] dp = new int[nums.length];
        dp[0] = nums[0];

        int max = dp[0];
        for (int i = 1; i < dp.length; i++) {
            dp[i] = nums[i];
            // Do not need to check k < i - 3.
            for (int j = 2; i - j >= 0 && j <= 3; j++) {
                dp[i] = Math.max(dp[i], dp[i - j] + nums[i]);
            }
            max = Math.max(dp[i], max);
        }

        return max;
    }
}

但一旦我选择了一行的最佳选择，它可能与该行上下的行的最佳选择不一致。即使我找到了两行的最佳组合，下一行的贵重物品可能比这两行的组合还要多，需要再做一次调整。
这是困难的，因为比单个行上的房子要考虑更多的变量，并且还可以有一个以上的最优排列，给盗贼最大的赃物（例如上面的例子）。
我确实在Python中找到了一个写得不好的解决方案，但是由于我只理解基于C语言（Java，C，C，C++），所以我不能从中得到很多。有人能帮我找个解决办法或者至少提些建议吗？
谢谢你的时间！

最佳答案

我查了你提到的代码。在我看来，使用flow的解决方案显然是错误的在有限的重量下，从源到汇没有路径这个解决方案基本上像棋盘一样给网格上色，并选择所有的黑色方块或所有的白色方块在以下情况下，这不是最佳选择：

1     500
300   1
1000  300

最好选择1000和500，但该解决方案将选择300+300+500。
动态规划解是指数型的。
我的数学知识不足以理解LP解。
很抱歉没有回答你的问题。

关于algorithm - 二维房屋强盗算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/50830647/