房子抢劫犯的问题如何这样做

Question

null

null

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

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