入室抢劫问题如何做到这一点

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;
}
}

当数组长度为奇数时如何执行此逻辑？我们可以这样做吗？即使长度相同，输出也是正确的

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);
}

使用 dp 可以优化上述解决方案的时间和空间复杂度。您可以跟踪两个值：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;
}