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 次阅读