【每日算法Day 105】打家劫舍第二弹:看好你的电瓶车!

题目链接

LeetCode 213. 打家劫舍 II

往期回顾:打家劫舍 I :
【每日算法Day 104】偷电瓶的周某今天放出来了,还不赶紧做这道题防范一下!

题目描述

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

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

示例1

输入:
[2,3,2]
输出:
3

示例2

输入:
[1,2,3,1]
输出:
4

题解

这题和上一题唯一区别就是首尾只能选一个偷,那么我们可以分为两种情况。

如果不偷第一个,那么问题就变成了在后 $n-1$ 个里面偷取的最大价值。

如果不偷最后一个,那么问题就变成了在前 $n-1$ 个里面偷取的最大价值。

而这两个转化后的问题就没有首尾连接的约束了,可以直接采用上一题的解法求解,转移方程还是:
$$
dp[i] = \max{\{dp[i-1], dp[i-2]+p[i]\}}
$$

最终取两种情况的较大值就行了。

代码

c++

class Solution {
public:
    int rob1(vector<int>& nums, int l, int r) {
        int prepre = 0, pre = 0, now = 0;
        for (int i = l; i <= r; ++i) {
            now = max(pre, prepre+nums[i]);
            prepre = pre;
            pre = now;
        }
        return now;
    }

    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 1) return nums[0];
        int a = rob1(nums, 0, n-2);
        int b = rob1(nums, 1, n-1);
        return max(a, b);
    }
};

关注公众号【算法码上来】,每日算法干货马上就来!


   转载规则


《【每日算法Day 105】打家劫舍第二弹:看好你的电瓶车!》 韦阳 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
【每日算法Day 106】打家劫舍系列最后一弹,撑住你就赢了! 【每日算法Day 106】打家劫舍系列最后一弹,撑住你就赢了!
题目链接LeetCode 337. 打家劫舍 III 往期回顾:打家劫舍 I :【每日算法Day 104】偷电瓶的周某今天放出来了,还不赶紧做这道题防范一下! 往期回顾:打家劫舍 II :【每日算法Day 105】打家劫舍第二弹:看好你的电
2020-04-20
下一篇 
【每日算法Day 104】偷电瓶的周某今天放出来了,还不赶紧做这道题防范一下! 【每日算法Day 104】偷电瓶的周某今天放出来了,还不赶紧做这道题防范一下!
偷电瓶的周某今天(2020.04.18)出来啦,打工是不可能打工的,这辈子都不可能打工的,大家可要小心咯。今天开始讲解 LeetCode 打家劫舍系列三道题目,给大家防范一下! 题目链接LeetCode 198. 打家劫舍 题目描述 题
2020-04-18
  目录