【LeetCode: 剑指 Offer II 090. 环形房屋偷盗（打家窃舍） | 暴力递归=＞记忆化搜索=＞动态规划】-Toy模板网

这篇具有很好参考价值的文章主要介绍了【LeetCode: 剑指 Offer II 090. 环形房屋偷盗（打家窃舍） | 暴力递归=＞记忆化搜索=＞动态规划】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

【LeetCode: 剑指 Offer II 090. 环形房屋偷盗（打家窃舍） | 暴力递归=＞记忆化搜索=＞动态规划】

🍎作者简介：硕风和炜，CSDN-Java领域新星创作者🏆，保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🍎座右铭：人生如棋，我愿为卒，行动虽慢，可谁曾见我后退一步？🎯🎯🎯

【LeetCode: 剑指 Offer II 090. 环形房屋偷盗（打家窃舍） | 暴力递归=＞记忆化搜索=＞动态规划】

题目回顾

大家再看这道题目之前，可以先去看一下我之前写过的一篇关于打家窃舍算法题的博客，再看这个这更容易理解了。
博客的地址放到这里了，可以先去学习一下这到题目。
【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]);
    }
}

运行结果

【LeetCode: 剑指 Offer II 090. 环形房屋偷盗（打家窃舍） | 暴力递归=＞记忆化搜索=＞动态规划】

记忆化搜索

求解思路

根据我们递归的分析，在递归的过程中会产生重复的子过程，所以我们想到了加一个缓存表，也就是我们的记忆化搜索。

实现代码

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]);
    }
}

运行结果

【LeetCode: 剑指 Offer II 090. 环形房屋偷盗（打家窃舍） | 暴力递归=＞记忆化搜索=＞动态规划】

动态规划

求解思路

接下来我们根据之前的递归思路以及记忆化缓存改写动态规划。

实现代码

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]);
    }
}