题目回顾
大家再看这道题目之前，可以先去看一下我之前写过的一篇关于打家窃舍算法题的博客，再看这个这更容易理解了。
博客的地址放到这里了，可以先去学习一下这到题目。
【LeetCode: 剑指 Offer II 089. 房屋偷盗（打家窃舍） | 暴力递归=＞记忆化搜索=＞动态规划】
题目链接
剑指 Offer II 090. 环形房屋偷盗
213. 打家劫舍 II
题目描述
一个专业的小偷，计划偷窃一个环形街道上沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组 nums ，请计算 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
示例 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: 剑指 Offer II 089. 房屋偷盗（打家窃舍） | 暴力递归=＞记忆化搜索=＞动态规划】
- 该题目不同之处在于题目的限制是环形的，如果我们偷取了第一家，那么最后一家肯定是不能偷的；反之，如果我们第一家没有偷取，那么是可以偷取最后一家的。
- 下面就是具体代码实现的一些细节需要做出改变，其它无需改变。
实现代码
class Solution {
public int rob(int[] nums) {
int n=nums.length;
return Math.max(nums[0]+process(2,n-1,nums),process(1,n,nums));
}
public int process(int index,int n,int[] nums){
if(index>=n) return 0;
return Math.max(process(index+1,n,nums),process(index+2,n,nums)+nums[index]);
}
}
运行结果
记忆化搜索
求解思路
- 根据我们递归的分析，在递归的过程中会产生重复的子过程，所以我们想到了加一个缓存表，也就是我们的记忆化搜索。
实现代码
class Solution {
public int rob(int[] nums) {
int n=nums.length;
int[] dp1=new int[n+1];
int[] dp2=new int[n+1];
Arrays.fill(dp1,-1);
Arrays.fill(dp2,-1);
return Math.max(nums[0]+process(2,n-1,nums,dp1),process(1,n,nums,dp2));
}
public int process(int index,int n,int[] nums,int[] dp){
if(index>=n) return 0;
if(dp[index]!=-1) return dp[index];
return dp[index]=Math.max(process(index+1,n,nums,dp),process(index+2,n,nums,dp)+nums[index]);
}
}
运行结果
动态规划
求解思路
- 接下来我们根据之前的递归思路以及记忆化缓存改写动态规划。
实现代码
class Solution {
public int rob(int[] nums) {
int n=nums.length;
int[] dp1=new int[n+10];
int[] dp2=new int[n+10];
for(int index=n-2;index>=0;index--){
dp1[index]=Math.max(dp1[index+1],dp1[index+2]+nums[index]);
}
for(int index=n-1;index>=0;index--){
dp2[index]=Math.max(dp2[index+1],dp2[index+2]+nums[index]);
}
return Math.max(nums[0]+dp1[2],dp2[1]);
}
}
运行结果
共勉
最后，我想送给大家一句一直激励我的座右铭，希望可以与大家共勉！