【4.15】LeetCode每日一题· 打家劫舍 II

2021年04月15日 14时05分

标签： LeetCode 动态规划

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

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

#### 示例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 = [0]
输出：0
```

#### 提示
```
1 <= nums.length <= 100
0 <= nums[i] <= 1000
```

#### 来源
> 来源：力扣（LeetCode）
> 链接：[题目链接](https://leetcode-cn.com/problems/house-robber-ii "题目链接")

## 解题思路
环形dp，破环成链。

如果房屋不连成一个环，定义状态`dp[i][0]`和`dp[i][1]`：
```
dp[i][0] := 偷到第i个房子且不偷第i个房子所能得到的最高金额
dp[i][1] := 偷到第i个房子且偷第i个房子所能得到的最高金额
```

那么可以得出如下状态转移方程：
```
dp[i][0] = max(dp[i-1][0], dp[i-1][1])
dp[i][1] = dp[i-1][0] + nums[i];
```

由于本题中，第一个房子是否偷的情况会影响最后一个房子是否可以被偷，因此可以进行讨论。

1. 强制第一个房子被偷，则最后一个房子不能被偷。此时
	```
	dp[0][0] = 0
	dp[0][1] = nums[0]
	```
	最后答案`res0 = dp[N-1][0]`（设房屋总数为`N`）。
	
2. 强制第一个房子不被偷，那么最后一个房子可以被偷也可以不被偷。强制第一个房子不被偷可以等价于**偷第一个房子获得的金额为0**，因此有
	```
	dp[0][0] = dp[0][1] = 0
	```
	最后答案为`res1 = max(dp[N-1][0], dp[N-1][1])`。
因此最后取`res0`和`res1`的较大值即为答案。

⚠️注意：需要特别注意的一点时，**当房屋数量为1时上述算法不成立**（因为此时第一个房子也是最后一个房子，导致**讨论1**中取`dp[0][0] = 0`，且**讨论2**中`dp[0][0] = dp[0][1] = 0`，因此输出必定为0），需要进行特判。第一次就WA在了这个点上。

## 代码
```cpp
class Solution {
public:
    // dp[i][0] := 偷到第i个房子且不偷第i个房子所能得到的最高金额
    // dp[i][1] := 偷到第i个房子且偷第i个房子所能得到的最高金额
    // dp[i][0] = max(dp[i-1][0], dp[i-1][1])
    // dp[i][1] = dp[i-1][0] + nums[i];
    int rob(vector<int>& nums) {
        const int N = nums.size();
        // 只有一个房子就偷着一个
        if(N == 1) return nums[0];
        int dp[N][2], res0 = 0, res1 = 0;
        // 偷第一个房子
        dp[0][0] = 0;
        dp[0][1] = nums[0];
        for(int i = 1; i < N; i++){
            dp[i][0] = max(dp[i-1][0], dp[i-1][1]);
            dp[i][1] = dp[i-1][0] + nums[i];
        }
        // 最后一个房子没法偷
        res0 = dp[N-1][0];
        
        // 不偷第一个房子
        dp[0][0] = 0;
        dp[0][1] = 0;
        for(int i = 1; i < N; i++){
            dp[i][0] = max(dp[i-1][0], dp[i-1][1]);
            dp[i][1] = dp[i-1][0] + nums[i];
        }
        // 最后一个房子可以偷也可以不偷
        res1 = max(dp[N-1][0], dp[N-1][1]);
        return max(res0, res1);
    }
};
```

## 用时和内存
> 执行用时：0 ms，在所有 C++提交中击败了100.00%的用户
> 内存消耗：7.6 MB，在所有 C++提交中击败了79.91%的用户

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【4.15】LeetCode每日一题· 打家劫舍 II

所有评论

暂无评论

新增评论