java - 房子强盗问题如何这样做

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