题目链接:213. 打家劫舍 II - 力扣(LeetCode)
前情提要:
本体是打家劫舍的一个变形题,希望大家能先做198. 打家劫舍 - 力扣(LeetCode),并看一下我上题的讲解力扣198-打家劫舍(Java详细题解)-CSDN博客,再看本题会觉得非常简单。
因为本人最近都来刷dp类的题目所以该题就默认用dp方法来做。
dp五部曲。
1.确定dp数组和i下标的含义。
2.确定递推公式。
3.dp初始化。
4.确定dp的遍历顺序。
5.如果没有ac打印dp数组 利于debug。
每一个dp题目如果都用这五步分析清楚,那么这道题就能解出来了。
题目思路:
其实本题与打家劫舍1唯一的区别就在于不能首尾同时偷了,只能选择其一进行偷窃。
有很多人会想复杂,这些房间都连接成环了,我该怎么确定起始和终止位置呢?
其实我们将这个环形问题分解为线性问题就好。
既然首尾有约束,我们就判断首尾的情况。
大概有三种。
首尾都不考虑偷
首考虑偷,尾部偷
尾考虑偷,首不偷
其实1这种情况在2,3中都考虑进去了,我们就考虑2,3就好。
首考虑偷,尾考虑不偷,那我们就不把最后一个元素放入我们的dp数组。把一个环形问题就划分为了线性问题。
核心处理逻辑代码还是打家劫舍1的代码,只不过把他做成一个函数,把首的坐标和尾前一个坐标传入即可,这样就把尾元素排除了。
尾考虑偷,首考虑不偷,也是如此,把尾坐标和首后一个坐标传入即可。
虽然我们将整个环的问题分解成了俩个子问题。
但我们还是要求整个环的最大金额。
怎么办?
其实就对这俩种情况再取一个最大即可。
因为本题与打家劫舍1思路差别不大,我就不用动规五部曲分析了。
最终代码:
class Solution {public int rob(int[] nums) {// 该题给了我们一个限制 首尾是相邻的//那么该题可以分为俩种情况 第一种情况考虑首不考虑尾部//第二种情况 考虑尾部不考虑首部//这俩种情况我们再取一个最大值,就能得出偷窃到的最高金额//将环形的问题展开 转化为线性问题 再单独去考虑首尾元素if(nums.length == 1)return nums[0];return Math.max(rob1(nums,0,nums.length - 2),rob1(nums,1,nums.length - 1));}public int rob1(int[] nums,int start,int end) {//这里是将传入的下标做一个特判 如果end == start 就不会有dp[start + 1]if(start == end)return nums[start];int [] dp = new int [nums.length + 1];dp[start] = nums[start];dp[start + 1] = Math.max(nums[start],nums[start + 1]);for(int i = start + 2;i <= end;i++){dp[i] = Math.max(dp[i - 2] + nums[i],dp[i - 1]);}return dp[end];}
}
这一篇博客就到这了,如果你有什么疑问和想法可以打在评论区,或者私信我。
我很乐意为你解答。那么我们下篇再见!