当前位置：首页 > article >正文

leetcode 打家劫舍

article 2024/9/22 0:55:01

打家劫舍

(a)
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

示例 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 。

(b)
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，今晚能够偷窃到的最高金额。

示例 1：

输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。
示例 2：

输入：nums = [1,2,3,1]
输出：4
解释：你可以先偷窃 1 号房屋（金额 = 1），然后偷窃 3 号房屋（金额 = 3）。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 3：

输入：nums = [1,2,3]
输出：3

(a)

已知当房子数目为0时，获得的收益为0，房子数目为1时获得的收益为从第1间房子获得，房子数目为2时获得的收益从一二两间房子中的最大值者获得。当i>2时，获得的最大收益为dp[i]=max(dp[i-1],dp[i-2]+nums[i])，其中dp[i]表示从前i间房子获得的最大收益，其中前i个房子的收益为前i-1件房子的最大收益或者前i-2间房子的最大收益与第i间房子的最大收益中的最大值

其中最优子结构为：dp[i]表示从前i间房子获得的最大收益

状态转移方程：dp[i]=max(dp[i-1],dp[i-2]+nums[i])

int rob(vector<int> &nums) {
    int l = nums.size();
    if (l == 0) {
        return 0;
    } else if (l == 1) {
        return nums[0];
    } else if (l == 2) {
        return nums[1] > nums[0] ? nums[1] : nums[0];
    } else {
        int dp[110] = {0};//dp[i]前i个房子可获得的最大收益
        dp[0] = nums[0];
        dp[1] = nums[1] > nums[0] ? nums[1] : nums[0];
        for (int i = 2; i < l; ++i) {
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[l - 1];
    }
}

其中时间复杂度为： $O (n)$ ，空间复杂度为： $O (n)$

(b)

对于首尾相连的情况，即把（a）中可以拆分为选取第一个不选取最后一个，选取最后一个，而不选取第一个两种情况，并选取两种情况中最大的那个

已知当房子数目为0时，获得的收益为0，房子数目为1时获得的收益为从第1间房子获得，房子数目为2时获得的收益从一二两间房子中的最大值者获得。当i>2时，dp1[i]表示选取第一个，而不选取最后一个的情况下，选取前i个房子可以获得的最大收益，dp2[i]表示选取最后一个，而不选取第一个的情况，选取前i个房子可以获得的最大收益，最后返回结果为max(dp1[l - 2], dp2[l-1])

其中最优子结构为：dp1[i]表示选取第一个，而不选取最后一个的情况下，选取前i个房子可以获得的最大收益，dp2[i]表示选取最后一个，而不选取第一个的情况，选取前i个房子可以获得的最大收益

状态转移方程：dp1[i]=max(dp1[i-1],dp1[i-2]+nums[i])与dp2[i]=max(dp2[i-1],dp2[i-2]+nums[i])

int rob(vector<int> &nums) {
    int l = nums.size();
    if (l == 0) {
        return 0;
    } else if (l == 1) {
        return nums[0];
    } else if (l == 2) {
        return nums[1] > nums[0] ? nums[1] : nums[0];
    } else {
        int dp1[110] = {0};//dp1[i]前i个房子可获得的最大收益
        dp1[0] = nums[0];
        dp1[1] = nums[1] > nums[0] ? nums[1] : nums[0];
        for (int i = 2; i < l; ++i) {
            dp1[i] = max(dp1[i - 1], dp1[i - 2] + nums[i]);
        }

        int dp2[110] = {0};
        dp2[0] = 0;
        dp2[1] = nums[1];
        dp2[2] = nums[1] > nums[2] ? nums[1] : nums[2];
        for (int i = 3; i < l; ++i) {
            dp2[i] = max(dp2[i - 1], dp2[i - 2] + nums[i]);
        }
        if (l == 3) {
            dp2[l] = dp2[2];
        }
        return max(dp1[l - 2], dp2[l - 1]);
    }
}