LeetCode 动态规划 打家劫舍 II

打家劫舍 II

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
示例 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
提示：
1 <= nums.length <= 100
0 <= nums[i] <= 1000

题解

这道题相对于打家劫舍，仅仅是多了一个限制条件

第一个房屋和最后一个房屋是紧挨着

也就是说

第一个房屋和最后一个房屋是不能同时偷的

那么这个条件对于我们分析问题有什么影响嘛

因为我们是不知道对于第一个和最后一个房屋中偷哪一个的

所以不妨分为两种情况

偷第一个，那么最后一个就不能偷，数组的下标范围是 0 到 numsSize-2

偷最后一个，那么第一个就不能偷，数组的下标范围是 1 到 numsSize-1

然后选择这两种情况中的最大值即可

对于这两种情况的计算便与打家劫舍相同了

首先初始化数组前两个的数据

使用两个变量 pre 和 cur 代表 i 位置前两个与前一个的偷得的最大值

然后从下标 2（或3）开始遍历数组

对于下标 i 的数据

它只有偷和不偷这两种选择

如果偷了，它得到的值就是 num[i] + pre

否则就是 cur

选择其中大的结果

然后更新 pre 和 cur

遍历完数组之后

cur 就是能偷到的最大的值

两种情况中最大的cur就是答案

代码如下↓

int rob(int* nums, int numsSize) {
    if(numsSize==1)
    {
        return nums[0];
    }
    if(numsSize==2)
    {
        return fmax(nums[0],nums[1]);
    }
    int pre1=nums[0];
    int cur1=nums[0];
    for(int i=2;i<numsSize-1;i++)//偷第一家
    {
        if(nums[i]+pre1>cur1)
        {
            int x=pre1;
            pre1=cur1;
            cur1=nums[i]+x;
        }
        else
        {
            pre1=cur1;
        }
    }
    int pre2=nums[1];
    int cur2=fmax(nums[1],nums[2]);
    for(int i=3;i<numsSize;i++)//不偷第一家
    {
        if(nums[i]+pre2>cur2)
        {
            int x=pre2;
            pre2=cur2;
            cur2=nums[i]+x;
        }
        else
        {
            pre2=cur2;
        }
    }
    return cur1>cur2?cur1:cur2;
}