题目描述
这是 LeetCode 上的 213. 打家劫舍 II ，难度为 中等。
Tag : 「线性 DP」
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。
这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。
同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
示例 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
动态规划
在 198. 打家劫舍 中，并没有「第一间」和「最后一间」不能同时选择的限制，因此我们从头到尾做一遍 DP 即可。
在 198. 打家劫舍 中，我们可以将状态定义为两维：
f[i][j]f[i][j] 代表考虑前 ii 个房间，当前 ii 房间的现在状态为 jj 的最大价值。
- f[i][0]f[i][0] 代表考虑前 ii 个房间，并且「不选」第 ii 个房间的最大价值。由于已经明确了第 ii 个房间不选，因此 f[i][0]f[i][0] 可以直接由 max(f[i - 1][0], f[i - 1][1])max(f[i−1][0],f[i−1][1]) 转移而来。
- f[i][1]f[i][1] 代表考虑前 ii 个房间，并且「选」第 ii 个房间的最大价值。由于已经明确了第 ii 个房间被选，因此 f[i][1]f[i][1] 直接由 f[i - 1][0] + nums[i]f[i−1][0]+nums[i] 转移过来。
到这里，你已经解决了 198. 打家劫舍 了。
对于本题，由于只是增加了「第一间」和「最后一间」不能同时选择的限制。
通常，对于一些明显不是「增加维度」的新限制条件，我们应当考虑直接将其拎出讨论，而不是多增加一维进行状态记录。
我们可以把「第一间」&「最后一间」单独拎出来讨论：
- 明确「不选」第一间：
- 初始化 f[0][0]f[0][0] 和 f[0][1]f[0][1]，均为 00。
- 先从「第二间」开始递推到「倒数第二间」的最大价值。
- 再处理「最后一间」的情况：由于明确了「不选第一间」，则最后的最大价值为 max(f[n - 2][1], f[n - 2][0] + nums[n - 1])max(f[n−2][1],f[n−2][0]+nums[n−1])。
- 允许「选」第一间：
- 初始化 f[0][0]f[0][0] 和 f[0][1]f[0][1]，分别为 00 和 nums[0]nums[0]。
- 先从「第二间」开始递推到「倒数第二间」的最大价值。
- 再处理「最后一间」的情况：由于明确了「选第一间」，则最后的最大价值为 max(f[n - 2][0], f[n - 2][1])max(f[n−2][0],f[n−2][1])。
走完两遍 DP 后，再从两种情况的最大价值中再取一个 maxmax 即是答案。
代码：
class Solution { public int rob(int[] nums) { int n = nums.length; if (n == 0) return 0; if (n == 1) return nums[0]; // 第一间「必然不选」的情况 int[][] f = new int[n][2]; for (int i = 1; i < n - 1; i++) { f[i][0] = Math.max(f[i - 1][0], f[i - 1][1]); f[i][1] = f[i - 1][0] + nums[i]; } int a = Math.max(f[n - 2][1], f[n - 2][0] + nums[n - 1]); // 第一间「允许选」的情况 f[0][0] = 0; f[0][1] = nums[0]; for (int i = 1; i < n - 1; i++) { f[i][0] = Math.max(f[i - 1][0], f[i - 1][1]); f[i][1] = f[i - 1][0] + nums[i]; } int b = Math.max(f[n - 2][0], f[n - 2][1]); return Math.max(a, b); } } 复制代码
- 时间复杂度：O(n)O(n)
- 空间复杂度：O(n)O(n)
空间优化
不难发现，我们状态转移最多依赖到前面的 1 行，因此可以通过很机械的「滚动数组」方式将空间修改到 O(1)O(1)。
代码：
class Solution { public int rob(int[] nums) { int n = nums.length; if (n == 0) return 0; if (n == 1) return nums[0]; // 第一间「必然不选」的情况 int[][] f = new int[2][2]; for (int i = 1; i < n - 1; i++) { f[i%2][0] = Math.max(f[(i - 1)%2][0], f[(i - 1)%2][1]); f[i%2][1] = f[(i - 1)%2][0] + nums[i]; } int a = Math.max(f[(n - 2)%2][1], f[(n - 2)%2][0] + nums[n - 1]); // 第一间「允许选」的情况 f[0][0] = 0; f[0][1] = nums[0]; for (int i = 1; i < n - 1; i++) { f[i%2][0] = Math.max(f[(i - 1)%2][0], f[(i - 1)%2][1]); f[i%2][1] = f[(i - 1)%2][0] + nums[i]; } int b = Math.max(f[(n - 2)%2][0], f[(n - 2)%2][1]); return Math.max(a, b); } } 复制代码
- 时间复杂度：O(n)O(n)
- 空间复杂度：O(1)O(1)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.213 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour…
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
