leetcode 213.打家劫舍 II
题目描述
你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组,计算你在不触动警报装置的情况下,能够偷窃到的最高金额。
示例 1:
输入: [2,3,2]
输出: 3
解释: 你不能先偷窃1
号房屋(金额 = 2),然后偷窃3
号房屋(金额 = 2), 因为他们是相邻的。
示例 2:
输入: [1,2,3,1]
输出: 4
解释: 你可以先偷窃1
号房屋(金额 = 1),然后偷窃3
号房屋(金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
递归
注意!!这道题的求解过程是完全基于【打家劫舍 I】来的,递归的解法、动态规划解法、以及动态规划+空间压缩都是套用了【打家劫舍 I】。
如果没有看过【打家劫舍 I】,请一定要先看一遍,点击【这里】查看。
【打家劫舍 I】本质是基于一维数组的,而【打家劫舍 II】是一个环形数组。
直接用【打家劫舍 I】的代码会有什么问题呢?
因为是环形数组,所以第二排的数组的求解方式就不对了,1
和5
因为是首尾相连只能二选一。
而第三排数组的求解是满足要求的,只选了1
,没有选5
所以我们可以改成这样:
我们将原数组拆成两部分
1、nums[0],num[1]…num[end-1]
2、nums[1],nums[2]…nums[end]
然后我们分别对这两个数组求最大值,这个求解过程就完全套用了【打家劫舍 I】的逻辑。
我们只需要用同样的逻辑,执行两边代码,最后求两次的最大值即可。
递归的逻辑就是求两遍数组、动态规划也是求两遍、动态规划+压缩也一样。
到这里就很明确了,所谓的【打家劫舍 II】,其实就是执行了两遍的【打家劫舍 I】而已。
java代码:
class Solution { public int rob(int[] nums) { if(nums==null || nums.length==0) { return 0; } if(nums.length<=2) { return (nums.length==2) ? Math.max(nums[0],nums[1]) : nums[0]; } int n = nums.length; //将原数组分拆分成两个数组,然后对两个数组分别求一次最大值 int a = dfs(Arrays.copyOfRange(nums,0,n-1),0,0); int b = dfs(Arrays.copyOfRange(nums,1,n),0,0); return Math.max(a,b); } //直接套用了【打家劫舍 I】的代码 private int dfs(int[] arr,int index,int status) { if(index<=arr.length) { return 0; } int a=0,b=0,c=0; a = dfs(arr,index+1,status); if(status==1) { b = dfs(arr,index+1,0); } else { c = dfs(arr,index+1,1)+arr[index]; } return Math.max(a, Math.max(b,c) ); } }
python代码:
class Solution(object): def rob(self, nums): if not nums: return 0 n = len(nums) if n<=2: return max(nums) # 直接套用了【打家劫舍 I】的代码 def dfs(arr,index,status): if index<=len(arr): return 0 a,b,c = 0,0,0 a = dfs(arr,index+1,status) if status: b = dfs(arr,index+1,0) else: c = dfs(arr,index+1,1)+arr[index] return max(a,b,c) # 将原数组分拆分成两个数组,然后对两个数组分别求一次最大值 a = dfs(nums[0:n-1],0,0) b = dfs(nums[1:],0,0) return max(a,b)
递归+记忆化
我们创建了两套缓存,然后分别调用了两次递归函数,这两个递归函数的逻辑跟【打家劫舍 I】几乎是一样的。
然后将两次的返回结果求最大值即可。
java代码:
class Solution { public int rob(int[] nums) { if(nums==null || nums.length==0) { return 0; } if(nums.length<=2) { return (nums.length==2) ? Math.max(nums[0],nums[1]) : nums[0]; } int n = nums.length; int[][] cache1 = new int[n][2]; int[][] cache2 = new int[n][2]; for(int i=0;<n;++i) { Arrays.fill(cache1[i],-1); Arrays.fill(cache2[i],-1); } //将原数组分拆分成两个数组,然后对两个数组分别求一次最大值 int a = dfs(cache1,Arrays.copyOfRange(nums,0,n-1),0,0); int b = dfs(cache2,Arrays.copyOfRange(nums,1,n),0,0); return Math.max(a,b); } //套用了【打家劫舍 I】的代码 private int dfs(int[][] cache,int[] arr,int index,int status) { if(index>=arr.length) { return 0; } if(cache[index][status]>-1) { return cache[index][status]; } int a=0,b=0,c=0; a = dfs(cache,arr,index+1,status); if(status==1) { b = dfs(cache,arr,index+1,0); } else { c = dfs(cache,arr,index+1,1)+arr[index]; } cache[index][status] = Math.max(a, Math.max(b,c) ); return cache[index][status]; } }
python代码:
class Solution(object): def rob(self, nums): if not nums: return 0 n = len(nums) if n<=2: return max(nums) # 套用了【打家劫舍 I】的代码 def dfs(cache,arr,index,status): if index>=len(arr): return 0 if (index,status) in cache: return cache[index,status] a,b,c = 0,0,0 a = dfs(cache,arr,index+1,status) if status: b = dfs(cache,arr,index+1,0) else: c = dfs(cache,arr,index+1,1)+arr[index] cache[index,status] = max(a,b,c) return cache[index,status] # 将原数组分拆分成两个数组,然后对两个数组分别求一次最大值 a = dfs(dict(),nums[0:n-1],0,0) b = dfs(dict(),nums[1:],0,0) return max(a,b)
动态规划
动态规划也是基于【打家劫舍 I】的。
你会发现这题会有点无聊,每种解法都是执行两遍【打家劫舍 I】。
这里我们创建两个dp
数组
dp1
计算的是nums[1],nums[2]...nums[end]
这个数组
dp2
计算的是nums[0],nums[1]...nums[end-1]
这个数组
dp1
是从nums[1]
开始的,所以初的前两个值
-
dp1[0]
就等于0 -
dp1[1]
等于nums[1]
同理,dp2
是从nums[0]
开始的,所以初始化的前两个值
-
dp2[0]
就等于nums[0]
-
dp2[1]
就等于max(nums[0],nums[1])
java代码:
class Solution { public int rob(int[] nums) { if(nums==null || nums.length==0) { return 0; } if(nums.length<=2) { return (nums.length==2) ? Math.max(nums[0],nums[1]) : nums[0]; } int n = nums.length; int[] dp1 = new int[n]; int[] dp2 = new int[n]; //初始化两个dp数组,dp1是计算的是[1,end],dp2计算的是[0,end-1] dp1[0] = 0; dp1[1] = nums[1]; dp2[0] = nums[0]; dp2[1] = Math.max(nums[0],nums[1]); //按照【打家劫舍 I】的转移方式执行两遍 for(int i=2;i<n;++i) { dp1[i] = Math.max(dp1[i-1],dp1[i-2]+nums[i]); } for(int i=2;i<n-1;++i) { dp2[i] = Math.max(dp2[i-1],dp2[i-2]+nums[i]); } return Math.max(dp1[n-1],dp2[n-2]); } }
python代码:
class Solution(object): def rob(self, nums): if not nums: return 0 n = len(nums) if n<=2: return max(nums) dp1 = [0 for _ in xrange(n)] dp2 = [0 for _ in xrange(n)] # 初始化两个dp数组,dp1是计算的是[1,end],dp2计算的是[0,end-1] dp1[0] = 0 dp1[1] = nums[1] dp2[0] = nums[0] dp2[1] = max(nums[0],nums[1]) # 按照【打家劫舍 I】的转移方式执行两遍 for i in xrange(2,n): dp1[i] = max(dp1[i-1],dp1[i-2]+nums[i]) for i in xrange(2,n-1): dp2[i] = max(dp2[i-1],dp2[i-2]+nums[i]) return max(dp1[-1],dp2[-2])
动态规划+空间压缩
【打家劫舍 I】中我们用两个变量来优化空间,因为dp[i]
的值只需要用到dp[i-2]
和dp[i-1]
。
所以我们用两个变量来代替dp[i-2]
,dp[i-1]
然后不断滚动更新这两个变量,这里就是执行两遍。
java代码:
class Solution { public int rob(int[] nums) { if(nums==null || nums.length==0) { return 0; } if(nums.length<=2) { return (nums.length==2) ? Math.max(nums[0],nums[1]) : nums[0]; } int n = nums.length; //执行两遍,第一次求nums[0,n-1],第二次求nums[1,n],再返回两次计算的最大值 int a = dp(nums,0,n-1); int b = dp(nums,1,n); return Math.max(a,b); } //用滚动数组的方式优化空间 private int dp(int[] nums,int begin,int end) { int pre = 0; int cur = 0; for(int i=begin;i<end;++i) { int tmp = cur; cur = Math.max(cur,pre+nums[i]); pre = tmp; } return cur; } }
python代码:
class Solution(object): def rob(self, nums): if not nums: return 0 n = len(nums) if n<=2: return max(nums) # 用滚动数组的方式优化空间 def dp(begin,end): pre,cur = 0,0 for i in xrange(begin,end): cur,pre = max(cur,pre+nums[i]),cur return cur # 执行两遍,第一次求nums[0,n-1],第二次求nums[1,n],再返回两次计算的最大值 return max( dp(0,n-1),dp(1,n) )
推荐阅读:
12 次阅读