房屋抢劫问题如何解决这个问题

Question

你是一名专业强盗，计划抢劫一条街上的房屋。每个房屋都存有一定数量的钱，唯一阻止你抢劫他们的限制是相邻的房屋都连接着安保系统，如果同一晚上两个相邻的房屋被闯入，它会自动联系警察。

给定一个非负整数列表代表每个房屋的金额，请确定今晚你可以在不引起警察注意的情况下抢到的最大金额。

示例1：

输入：[1,2,3,1]

输出：4

说明：抢劫第1个房子（金额=1），然后抢劫第3个房子（金额=3）。你可以抢到的总金额为1+3=4。

示例2：

输入：[2,7,9,3,1]

输出：12

说明：抢劫第1个房子（金额=2），抢劫第3个房子（金额=9）和抢劫第5个房子（金额=1）。你可以抢到的总金额为2+9+1=12。

class Solution {
public int rob(int[] nums) {
    int sim=0;
    int sum=0;
    int i,j;

    for(i=0;i<nums.length;i++,i++){
        sim+=nums[i];
    }
    for(j=1;j<nums.length;j++,j++){
        sum+=nums[j];
    }
    int r= Math.max(sim,sum);
    return r;
}
}

当数组长度为奇数时，如何处理这种逻辑？ 我们可以这样做，即使对于偶数长度的数组，输出也是正确的。

- Naveen Verma

---

就像我说的那样，你不使用数组nums，你的代码只关心构建索引的总和。 - Tom

如果(nums%length!=0)，我可以有什么中止条件……？ - Naveen Verma

如果在某些时候跳过超过1个房子更有优势怎么办呢？例如，[1, 3, 5, 2, 1, 7]。您的代码将检查[1, 5, 1]和[3, 2, 7]，但最佳解决方案是[1, 5, 7]，跳过索引3和4以选择索引5。 - siralexsir88

现在 Tom 怎么样了？但它仍然没有工作。 - Naveen Verma

Naveen，你修改了问题后中止条件就没问题了。 - Tom

Answer 1

你的解决方案是在抢劫前一个房子后跳过一个。这并不总是能够获得最大的收益。考虑这种情况：[100, 1, 1, 100]。根据你的解决方案，sim == 101 并且 sum == 101，然而，正确的解决方案应该是200（抢劫第0个和第3个房子）。

我提出了两种可能的解决方案：1.使用递归；2.使用DP。

使用递归，你可以选择抢劫一间房屋并跳过下一间，或者不抢劫一间房屋并去下一间。因此，你将有两种递归情况，这将导致O(2^n)时间复杂度和O(n)空间复杂度。

public int rob(int[] nums) {
    return robHelper(nums, 0, 0);
}

private int robHelper(int[] nums, int ind, int money) {
    if (ind >= nums.length) return money;

    int rec1 = robHelper(nums, ind+1, money);
    int rec2 = robHelper(nums, ind+2, money+nums[ind]);
    return Math.max(rec1, rec2);
}

使用动态规划可以从上面的解决方案中优化时间和空间复杂度。您可以跟踪两个值：currMax和prevMax。 当 prevMax 是除前一个房屋外最多的钱时， currMax 是考虑前一个房屋时的最大金额。 由于 prevMax 保证不包括前一个房屋的钱，因此可以将当前房屋的钱添加到 prevMax 中，并将其与 currMax 进行比较，以找到该点的总最大金额。这是我的使用dp的解决方案，时间复杂度为O（n），空间复杂度为O（1）：

public int rob(int[] nums) {
    int currmax = 0;
    int prevmax = 0;

    for (int i = 0; i < nums.length; i++) {
        int iSum = prevmax + nums[i];
        prevmax = currmax;
        currmax = Math.max(currmax, iSum);
    }
    return currmax;
}

- wWw

Answer 2

正如评论中siralexsir88所指出的，仅仅检查抢夺奇数/偶数编号房屋的解决方案是不够的，因为最佳策略可能是连续跳过多个房屋。

给定的例子说明了这一事实: 假设你有[1, 3, 5, 2, 1, 7]，这里的索引3和4必须被跳过，以选择后面的7。

提议的解决方案

这个问题是动态规划的典型示例，可以通过递归地建立解决方案来解决。

对于每个房子，有两种选择: 要么抢劫它，要么不抢。让我们跟踪两种情况下每个房子的最佳解决方案: 如果我们抢劫第i个房屋，则将R[i]命名为i的最大利润。如果我们不去抢劫第i个房屋，那么同样定义NR[i]。

例如，假设我们有[1, 3]。在这种情况下：

- R[0] = 1 - NR[0] = 0 - R[1] = 3，抢劫第一个房子的最佳利润为3 - NR[1] = 1，不抢劫第一个房子的最佳利润为1

我们还称P[i]为抢劫第i个房子给我们带来的利润。我们可以通过R和NR递归地构建解决方案。

1) R[i] = NR[i-1] + P[i]
2) NR[i] = max(NR[i-1], R[i-1])
3) R[0] = P[0]
4) NR[0] = 0

让我们来分解一下。

递归关系1）表示，如果我们抢劫第i个房子，则我们不能抢劫前一个房子，因此对于前一个房子，我们需要选择“未被抢劫”的最佳得分。

递归关系2）表示，如果我们不抢劫第i个房子，则我们的得分是抢劫或不抢劫前一个房子中最好的那个。这是有道理的，因为我们没有为总利润增加任何东西，只是保持迄今为止的最佳利润。

3）和4）只是第一个房子的初始条件，在这一点上应该很清楚。

这是一个伪Python片段，用于计算最佳利润：

P = [1, 3, 5, 2, 1, 7] # The houses
R = [0] * len(P)
NR = [0] * len(P)

R[0] = P[0]

# We skip index 0
for i in range(1, len(P)):
    R[i] = NR[i-1] + P[i]
    NR[i] = max(NR[i-1], R[i-1])

# The solution is the best between NR and R for the last house
print max(NR[-1], R[-1])

该解决方案意味着在遍历房屋时跟踪两个数组（R[i]和NR[i]），然后在最后比较结果。如果你只想要最大利润，你可以保留前一个房子的结果R和NR，并在继续移动时放弃它们。然而，如果你想知道哪个房子序列导致了最佳结果，你需要跟踪整个数组，完成后回溯并重建解决方案。

- Juan Manuel Fresia

Answer 3

private static int rob(int[] money) {
    int max = 0;

    for (int i = 0; i < money.length; i++) {
        int skips = 2;

        while (skips < money.length) {
            int sum = 0;

            for (int j = 0; j < money.length; j += skips) {
                sum += money[j];
            }

            if (sum > max) {
                max = sum;
            }
            skips++;
        }
    }

    return max;
}

- Jason