Leetcode.213 打家劫舍 II

题目链接

Leetcode.213 打家劫舍 II mid

题目描述

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

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

解法：动态规划

我们定义 $f(i,j)$ 表示 小偷能从区间$[i,j]$ 偷窃的最高金额。

对于第一个房间 $nums[0]$：

• 偷窃第一个房间 $nums[0]$，那么就不能偷 $nums[1]$ 和 $nums[n-1]$。所以在偷第一个房间 $nums[0]$ 的情况下，最多能偷 $nums[0]+f(2,n-2)$；
• 不偷第一个房间 $nums[0]$，那么最多能偷 $f(1,n-1)$;

---

我们定义 $f0$ 为 不偷第 $i$ 个房间能够偷窃的最高金额； $f1$ 为 偷第 $i$ 个房间能够偷窃的最高金额。

此时，小偷对第 $i+1$ 个房间做出选择，偷还是不偷：

• f 0 ′ = f 1 f0' = f1 f0′=f1；
• $new\_f=max(f1,f0+nums[i+1])$；
• f 1 ′ = n e w _ f f1' = new_f f1′=new_f；

时间复杂度：

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();

        auto fun = [&](int l,int r)->int{
            int f0 = 0 , f1 = 0;
            for(int i = l;i <= r;i++){
                int new_f = max(f1,f0 + nums[i]);
                f0 = f1;
                f1 = new_f;
            }
            return f1;
        };

        return max(nums[0] + fun(2,n - 2) , fun(1,n - 1));

    }
};