213. 打家劫舍 II
难度: 中等
来源: 每日一题 2023.08.18 延展
你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组,计算你 在不触动警报装置的情况下 ,今晚能够偷窃到的最高金额。
示例 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
class Solution {
public int rob(int[] nums) {
}
}
分析与题解
-
动态规划
这个题目是典型的动态规划问题, 但是这个问题相对于 198. 打家劫舍 来说, 多了一个条件, 那就是 这个地方所有的房屋都 围成一圈.
对于围成一个圆这个条件, 我们单独来分情况讨论, 对于普通情况, 主要是有以下两种情况的.
-
情况1: 当前房屋不偷, 但是前一个房屋偷
-
情况2: 前一个房屋不偷, 但是当前房屋偷.
那么就会有如下的状态转移方程.
dp[i] = Math.max(dp[i - 2] + nums[i], dp[i -1]);
对于初始状态, 我们需要设定
i = 0
和i = 1
两种情况.dp[0] = nums[0]; dp[1] = Math.max(nums[0], nums[1]);
对于, 围成圆的情况, 我们可以分两种情况讨论.
- 包含
起始点
, 不包含终点
. - 包含
终点
, 不包含起始点
.
这样,我们可以理清实际上一共有四种case需要处理.
-
length = 1;
-
length = 2;
-
length > 2, 包含
起始点
, 不包含终点
. -
length > 2, 包含
终点
, 不包含起始点
.
整体的解题思路如下所示.
class Solution { public int rob(int[] nums) { int length = nums.length; if(length == 1) { return nums[0]; } else if (length == 2) { return Math.max(nums[0], nums[1]); } return Math.max(robRang(nums, 0, length-2), robRang(nums, 1, length-1)); } public int robRang(int[] nums, int start, int end) { int first = nums[start]; int second = Math.max(nums[start], nums[start + 1]); for(int i = start + 2; i <= end; i++) { int temp = second; second = Math.max(first + nums[i], second); first = temp; } return second; } }
复杂度分析:
- 时间复杂度: O(n), 时间复杂度与
nums
长度相关. - 空间复杂度: O(1), 常量级别的空间复杂度.
结果如下所示.
-
Comments | 0 条评论