时间戳

首页 > 解决方案 > 强盗问题如何做到这一点

java - 强盗问题如何做到这一点

问题描述

你是一名专业的强盗，计划抢劫沿街的房屋。每栋房子都藏有一定数量的金钱，唯一阻止你抢劫的限制是相邻的房子都连接了安全系统，如果同一晚两栋相邻的房子被闯入，它会自动联系警察。

给定一个代表每所房子金额的非负整数列表，确定你今晚可以在不报警的情况下抢劫的最大金额。

示例 1：

示例 2：

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

当数组长度为奇数时如何执行此逻辑？我们可以这样做吗？虽然输出对于均匀长度是正确的

标签： javaarraysalgorithmdata-structures

解决方案

您的解决方案是在抢劫前一所房子后跳过一所房子。这并不总是提供最大的输出。考虑这种情况：[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;
}

推荐阅读